В магазине проводится акция. Вы можете купить несколько товаров, и самый дорогой достанется вам бесплатно! Но дело в том, что это очень необычный магазин, поэтому вы можете купить только непрерывный отрезок товаров.
Формально, товары представлены как массив $$$a$$$ длины $$$n$$$ из элементов неотрицательной стоимости. Стоимость $$$i$$$-го товара равна $$$a_i$$$ рублей. Вы можете выбрать любой непрерывный подотрезок и купить все товары на нём за сумму их стоимостей, не платя за самый дорогой.
Какое максимальное количество товаров вы можете купить, если вы можете потратить не более $$$s$$$ рублей.
В первой строке входных данных содержится два целых числа $$$n$$$ и $$$s$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq s \leq 10^{14}$$$) — количество товаров в магазине и количество имеющихся у вас денег соответственно.
Во второй строке входных данных содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — стоимости товаров.
Выведите одно целое число — максимальное количество товаров, которое вы можете купить.
1 9331054993288807670057
1
6 52 6 1 1 4 3
4
5 00 5 0 0 1
4
10 201 10 5 6 2 4 3 8 7 9
6
В первом примере из условия всего один товар. Один товар мы всегда можем купить бесплатно.
Во втором примере из условия можно купить четыре последних товара, потратив $$$5$$$ рублей.
В третьем примере из условия можно купить первые четыре товара, потратив $$$0$$$ рублей, так как самый дорогой товар нам достанется бесплатно.