Центр управления отправляет на Марс грузовую капсулу. Она может поднять не более \(W\) килограммов полезной нагрузки. Учёные отобрали \(n\) научных приборов, которые хотят отправить в этой миссии; масса каждого прибора равна \(w_i\) килограммов.
Каждый прибор можно либо отправить целиком, либо оставить на Земле — разбирать их на части нельзя. Место в капсуле есть: ограничение только по массе. Цель миссии — отправить максимальное количество разных приборов, чтобы провести как можно больше экспериментов (какие именно приборы полетят — неважно, лишь бы число было максимальным).
Помогите учёным определить, какое максимальное число приборов можно отправить одной капсулой.
Формат входных данных
В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 10^5\), \(1 \le W \le 10^9\)) — количество приборов и грузоподъёмность капсулы в килограммах.
Во второй строке — \(n\) целых чисел \(w_i\) (\(1 \le w_i \le 10^4\)), разделённых пробелами, — масса каждого прибора в килограммах.
Формат выходных данных
Одно целое число — максимальное количество приборов, которые можно отправить на Марс.
Примечание
В первом примере лучше всего отправить приборы массами \(1 + 2 + 3 + 4 = 10\) кг — ровно помещаются в капсулу, итого 4 прибора. Прибор массой 7 кг остаётся на Земле.
Во втором примере каждый прибор по отдельности весит больше грузоподъёмности капсулы. Ни один прибор отправить нельзя.
| № | Входные данные | Выходные данные |
|
1
|
5 10
3 1 7 2 4
|
4
|
|
2
|
3 5
6 8 10
|
0
|