Задача №115173. Задача в подарок
Ваша команда принимает участие в очередной олимпиаде. Всего в контесте \(n\) задач, \(i\)-я из них имеет сложность \(a_i\). Умственных возможностей вашей команды хватит на то, чтобы решить набор задач, с суммарной сложностью не более \(S\).
В конце контеста, после того, как вы уже решили сколько-то задач, вам может прийти озарение, и вы без затраты умственных усилий сможете решить еще одну любую задачу, если среди решенных вами задач, хотя бы половина не проще этой. После этого продолжить решать задачи вы не сможете. Обратите внимание, что даже если вы решили 0 задач, то в конце контеста можете без затраты умственных усилий решить любую задачу.
Сколько максимум задач вы можете решить за контест?
В первой строке вам даны два числа \(n, S\) (\(1 \leqslant n \leqslant 300000, 1 \leqslant S \leqslant 10^9\)) — количество задач в контесте, а также умственные возможности вашей команды.
Во второй строке записаны \(n\) чисел \(a_1, a_2, \ldots, a_n\) (\(1 \leqslant a_i \leqslant 10^9\)) — сложности задач.
Выведите единственное число — максимальное число задач, которое может решить ваша команда.
В первом примере с помощью умственных усилий можно решить задачи сложностью 4, 2, 1 и 5, а в конце контеста с помощью озарения решить задачу сложностью 3.
6 12 4 2 1 3 6 5
5
7 11 5 4 3 2 1 100 1000000000
4
3 100 100 101 101
1
2 3 5 105
1