Леді працює менеджером ресторану. В ресторані приготували ланч-боксів і Леді планує роздати їх в деякі школи. Припустимо, що є шкіл та -та школа замовляє k_i ланч-боксів.
Леді намагається поширювати ланч-бокси для максимально можливої кількості шкіл. Крім того, Леді забобонна, а тому у неї є правило – для -ої школи вона дає або нуль або k_i ланч-боксів.
Напишіть програму, яка допоможе Леді знайти максимальну кількість шкіл, які зможуть отримати ланч-бокси?
Перший рядок вхідного файлу містить 2 цілих числа і . Далі йдуть рядків: -й рядок містить ціле число k_i.
Виведіть у вихідний файл одне ціле число – максимальну кількість шкіл, які зможуть отримати ланч-бокси.
Приклад 1
Ланч-бокси зможуть отримати перша, третя та четверта школи.
Ця задача складається з трьох підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.
№ підзадачі | Бали | Обмеження | Примітка |
0 | 0 | Тести з умови | |
1 | 20 | M = 1; 1 \le N \le 60\,000; 1 \le k_i \le 30\,000 | |
2 | 30 | 1 \le M \le 1\,000; 1 \le N \le 60\,000; 1 \le k_i \le 1\,000 | |
3 | 50 | 1 \le M \le 60\,000; 1 \le N \le 60\,000; 1 \le k_i \le 30\,000 |