Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Уважаемые участники, убедитесь, что вы прочитали руководство (и особенно раздел «Полезные советы и важные замечания»)!
Сегодня в магазине одежды невероятная акция: «Купите одну вещь, и наберите бесплатно любое количество вещей, если их общая цена не превышает стоимости купленной вещи!»
Всего в магазине N вещей, i-я вещь стоит A[i] рублей. У Максима сегодня день рождения, и друзья согласились оплатить ему одну любую вещь из магазина. Какое максимальное количество вещей сможет получить Максим?
Входные данные
Входной поток в первой строке содержит целое число N (2 <= N <= 2000) — количество вещей в магазине.
Вторая строка содержит N целых чисел Ai (1 <= Ai <= 10^5) — стоимости вещей.
Выходные данные
Выведите одно целое число — максимальное количество вещей, которое сможет получить Максим.
Примеры
| Входные данные | Выходные данные |
5
5 3 2 1 4 | 3 |
2
6 6 | 2 |
Для отправки решений необходимо выполнить вход.
|