После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".

Остался непрояснённым только размер сцены. Сцена размера k может выдержать k коров, танцующих одновременно. n коров в стаде пронумерованы последовательно 1 .. n в порядке, в котором они должны появиться на сцене во время танца. Каждая корова i планирует танцевать определённое время d(i). Изначально коровы 1 .. k появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова k + 1 немедленно начинает танцевать и т.д. Поэтому всегда k коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени t.

Понятно, что чем больше значение k, тем меньше время t. Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница Tmax, указывающая максимально возможное значение величины t. Ваша задача - определить минимально возможное подходящее значение k.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 10000) и Tmax, где Tmax - целое число, не более 106.

Следующие n строк задают длительности танцев d(1) .. d(n) для коров 1 .. n. Каждое из d(i) - целое число в интервале 1 .. 105.

Гарантируется, что если k = n, шоу закончится вовремя.

Выходные данные

Выведите наименьшее возможное значение k такое, что танцевальное шоу закончится не более чем через Tmax единиц времени.