Masala tavsifi
Qirollik Kutubxonasida arxivchilar sehrli kitoblar yozadilar. Keyingi kitobni yakunlash uchun $i$-harf kamida $C[i]$ marta ishlatilishi kerak. Mamlakat $n$ ta harfdan iborat alifbodan foydalanishini unutmang.
Shtamp — ustiga $m$ ta harf yozilgan yopishqoq qog‘oz bo‘lagi (harflar takrorlanishi mumkin). Shtampning ko‘rinishi, unda qaysi harflar yozilgani va hokazolar oldindan kelishib olinadi va o‘zgartirib bo‘lmaydi. Shtampning ko‘rinishi kelishib olingandan so‘ng, ushbu kelishuv asosida cheksiz miqdorda shtamplar yaratiladi.
Kitob ushbu shtamplar yordamida chop etiladi. Kitobning bitta sahifasiga faqat bitta shtamp yopishtirilishi mumkin.
Agar siz shtamp dizayni uchun $m$ ta harfni tanlashingiz mumkin bo‘lsa, kitobni yozish uchun kerak bo‘ladigan sahifalarning minimal sonini toping.
Agar kitobni yozishning iloji bo‘lmasa, ya’ni hatto cheksiz miqdordagi shtamplar ham yetarli bo‘lmasa, unda $-1$ chiqaring.
### Kiritish formati
Birinchi qatorda $n$ --- alifbodagi harflar soni va $m$ --- shtampdagi harflar soni beriladi.
Ikkinchi qatorda $n$ ta butun son $C[i]$ --- kitobni yozish uchun $i$-harfning minimal talab qilinadigan soni beriladi.
**Cheklovlar:**
- $1 \leq n \leq 200\,000$
- $0 \leq m \leq 10^{18}$
- $0 \leq C[i] \leq 10^9$
### Chiqish formati
Siz shtampni loyihalayotganingizni hisobga olgan holda, kitobni yozish uchun sahifalarning minimal sonini chiqaring. Agar bu imkonsiz bo‘lsa, $-1$ chiqaring.
### Baholash
{|c|c|c|c|}
\hline
**Subtask** & **Qo‘shimcha cheklovlar** & **Ballar** & **Talab qilinadigan subtasks**
\hline
0 & Misoldagi testlar & 0 & ---
\hline
1 & $n \leq 20$; $C[i] \leq 20$ & 20 & 0
\hline
2 & $n \leq 1000$; $C[i] \leq 100$ & 10 & 0, 1
\hline
3 & $n \leq 1000$ & 30 & 0, 1, 2
\hline
4 & Qo‘shimcha cheklovlar yo‘q & 40 & 0, 1, 2, 3
\hline
### Izohlar
Birinchi testda, shtampda $2$ ta belgi sig‘sa ham, shtamplar soni qancha bo‘lishidan qat’i nazar, $3$ xil harfni hosil qilishning iloji yo‘q.