Олимпиадный тренинг

Задача . A. Флеш-карты


Задача

Темы: жадные алгоритмы реализация сортировки *800

У Эдварда есть n флеш-карт объемом a1, a2, ..., an мегабайт и большой файл размера m мегабайт.

Найдите минимальное количество флеш-карт, на которые можно записать файл Эдварда, если он может разделить свой файл на части произвольного размера.

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

В первой строке входных данных содержится целое положительных число n (1 ≤ n ≤ 100) — количество флеш-карт.

Во второй строке входных данных содержится целое положительное число m (1 ≤ m ≤ 105) — размер файла Эдварда в мегабайтах.

В следующих n строках входных данных содержится последовательность целых положительных чисел a1, a2, ..., an (1 ≤ ai ≤ 1000) — размеры флеш-карт в мегабайтах.

Гарантируется, что ответ существует, то есть сумма всех ai не меньше чем m.

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

В единственной строке выходных данных должно содержаться целое положительное число — минимальное количество флеш-карт, на которые можно записать файл Эдварда, если он может разделить свой файл на части произвольного размера.

Примечание

В первом тестовом примере Эдварду нужно 2 флеш-карты — первая и третья.

Во втором тестовом примере Эдварду нужны все 3 флеш-карты.

В третьем тестовом примере Эдварду нужна тольно одна флеш-карта и он может выбрать любую из имеющихся — либо первую, либо вторую.


Примеры
№Входные данныеВыходные данные
1 3
5
2
1
3 
2
2 3
6
2
3
2 
3
3 2
5
5
10 
1

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет