Коровье танцевальное шоу
После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".
Остался непрояснённым только размер сцены. Сцена размера k может выдержать k коров, танцующих одновременно. n коров в стаде пронумерованы последовательно 1 .. n в порядке, в котором они должны появиться на сцене во время танца. Каждая корова i планирует танцевать определённое время d(i). Изначально коровы 1 .. k появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова k + 1 немедленно начинает танцевать и т.д. Поэтому всегда k коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени t.
Понятно, что чем больше значение k, тем меньше время t. Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница T[max], указывающая максимально возможное значение величины t. Ваша задача - определить минимально возможное подходящее значение k.
Входные данные
Первая строка содержит n (1 ≤ n ≤ 10000) и T[max], где T[max] - целое число, не более 10^6.
Следующие n строк задают длительности танцев d(1) .. d(n) для коров 1 .. n. Каждое из d(i) - целое число в интервале 1 .. 10^5.
Гарантируется, что если k = n, шоу закончится вовремя.
Выходные данные
Выведите наименьшее возможное значение k такое, что танцевальное шоу закончится не более чем через T[max] единиц времени.