Masala B
Kompyuter xonalari
STEM musobaqasi maktabdagi kompyuter xonalarida o‘tkaziladi. Musobaqada jami \(K\) nafar o‘quvchi qatnashadi.
Maktabda \(N\) ta kompyuter xonasi bor. \(i-\) xonada \(a_i\) ta kompyuter mavjud. Bitta kompyuterda faqat bitta o‘quvchi ishlaydi.
Musobaqa vaqtida xavfsizlik va tartib uchun ishlatilgan har bir xonaga aynan bitta nazoratchi tayinlanadi. Agar xona ishlatilmasa, u qulflanadi va unga nazoratchi tayinlanmaydi.
Siz o‘quvchilarni xonalarga joylashtirishingiz kerak. Har bir o‘quvchi aynan bitta xonaga joylashtiriladi va \(i-\) xonaga joylashtirilgan o‘quvchilar soni \(a_i\) dan oshmasligi kerak.
Barcha \(K\) nafar o‘quvchini nazorat qilish uchun kerak bo‘ladigan eng kam nazoratchilar sonini aniqlang.
Birinchi qatorda ikkita butun son \(K\) va \(N\) - mos ravishda o'quvchilar va xonalar soni beriladi.
Ikkinchi qatorda \(N\) ta butun son \(a_1,a_2,…,a_N\) - har bir xonadagi kompyuterlar soni kiritiladi.
\(1 \le K \le 10^9\)
\(1 \le N \le 10^5\)
\(1 \le a_i \le 10^9\)
\(\sum_{i = 1}^{N}{a_i} \ge K\) ekanligi, ya'ni umumiy kompyuterlar soni barcha o'quvchilar sonidan kam emasligi kafolatlanadi.
O'quvchilarni qamrab olish uchun kerak bo'ladigan eng kam nazoratchilar sonini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
20 4 6 8 5 10 |
3 |
| 2 |
20 5 4 4 4 4 4 |
5 |
1-test holati uchun 3 ta nazoratchini 1, 2, va 4 xonalarga qo'yish mumkin, bunda barcha ishtirokchilar ushbu xonalarga joylashtiriladi.
2-test holati uchun esa barcha xonalar ishlatilishi shart, shuning uchun hamma xonaga bittadan nazoratchi talab qilinadi.
Telegram kanalimizga obuna bo'ling