Городские олимпиады/1-2 курсы/Предметная олимпиада по информатике 2019


4. Автомеханик (100 баллов)

Автор задачи: Ицков Алексей
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Сережа автомеханик. У него есть коробка, в которой x свободного места. У Сережи есть набор ключей, каждый из которых имеет свой размер a_i и будет занимать такое-же место в коробке. Выберите максимальное количество ключей разного размера, которые смогут поместиться в коробку.

Входные данные

В первой строке содержатся 2 целых числа n и x — количество ключей и максимальная вместимость коробки соответственно (2 \leqslant n \leqslant 1000, 0 \leqslant x \leqslant 10^5).

В следующей строке содержатся n чисел a_i — размер i-го ключа (1 \leqslant a_i \leqslant 1000).

Выходные данные

В единственной строке требуется вывести 1 целое число — максимальное количество ключей разного размера, которые смогут поместиться в коробку.

Примеры
Стандартный вводСтандартный вывод
3 10
7 5 2
2
5 22
7 12 3 8 5
3
Примечания

Решения, правильно работающие в случаях, когда повторяющихся размеров ключей нет, будут оцениваться из 24 баллов.

Решения, правильно работающие во всех случаях, будут оцениваться из 100 баллов.