Сколько покупок поместится в бюджет

После школы Миша зашёл в магазин у дома. У него есть ровно B рублей и список из n вещей, которые он *может* купить (каждую — не больше одного раза). Миша хочет унести как можно больше вещей.

Понятно, что если сначала брать более дешёвые вещи, шанс купить больше выше.

Твоя задача — узнать, сколько вещей максимум он сможет купить.

Важно: в олимпиадных задачах на других языках суммы могут не помещаться в 32-битный тип, поэтому обычно нужен 64-битный (int64). В Python это не проблема.

Формат ввода

В первой строке записаны два целых числа n и B — количество вещей и бюджет. Во второй строке записаны n целых чисел p1, p2, ..., pn — цены вещей.

Формат вывода

Выведи одно целое число — максимальное количество вещей, которые можно купить, не превышая бюджет B.

Ограничения

• 1 ≤ n ≤ 50000
• 0 ≤ B ≤ 1 000 000
• 1 ≤ pi ≤ 100 000

Пример

Ввод:

5 10
6 4 2 8 3

Вывод:

3

(Можно купить вещи за 2, 3 и 4 — всего 3 вещи, сумма 9.)

Ключевое наблюдение: чтобы унести максимум вещей при ограниченном бюджете, выгодно брать самые дешёвые. Если в каком-то наборе куплена дорогая вещь, а есть более дешёвая некупленная, то заменой дорогой на дешёвую мы не уменьшаем число вещей и только уменьшаем потраченную сумму. Значит, существует оптимальное решение, где куплены первые k цен после сортировки.

Почему работает жадность: после сортировки любой «пропуск» дешёвой вещи в пользу более дорогой не помогает купить больше предметов — он лишь съедает бюджет быстрее.

План решения:

• Считай n, B и массив цен.
• Отсортируй цены по возрастанию.
• Иди слева направо и накапливай сумму spent.
• Если следующая цена помещается, увеличивай spent и счётчик.
• Как только spent + p > B, можно остановиться: дальше цены не меньше, значит тоже не поместятся.

Мини-сниппет проверки: if spent + p <= B: spent += p; cnt += 1

Сложность: сортировка занимает O(n log n), проход — O(n). Память O(n).

Частая ошибка: не делать break после первой непоместившейся цены (после сортировки это уже бессмысленно) или копить сумму в слишком маленьком типе в других языках (нужен 64-битный).