Ланч-бокси#165

Ланч-бокси

1 секунда
512 мегабайтів
Середня

Леді працює менеджером ресторану. В ресторані приготували ланч-боксів і Леді планує роздати їх в деякі школи. Припустимо, що є шкіл та -та школа замовляє k_i ланч-боксів.

Леді намагається поширювати ланч-бокси для максимально можливої кількості шкіл. Крім того, Леді забобонна, а тому у неї є правило – для -ої школи вона дає або нуль або k_i ланч-боксів.

Напишіть програму, яка допоможе Леді знайти максимальну кількість шкіл, які зможуть отримати ланч-бокси?

Вхідні дані

Перший рядок вхідного файлу містить 2 цілих числа і . Далі йдуть рядків: -й рядок містить ціле число k_i.

Вихідні дані

Виведіть у вихідний файл одне ціле число – максимальну кількість шкіл, які зможуть отримати ланч-бокси.

Приклади

Приклад 1

Loading
Loading

Примітка

Ланч-бокси зможуть отримати перша, третя та четверта школи.

Оцінювання

Ця задача складається з трьох підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.

№ підзадачі

Бали

Обмеження

Примітка

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