После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное
представление - балет "Cowpelia".
Остался непрояснённым только размер сцены. Сцена размера \(K\) может выдержать
\(K\) коров, танцующих одновременно. \(N\) коров в стаде (\(1 \leq N \leq 10,000\))
пронумерованы последовательно \(1 \ldots N\) в порядке, в котором они должны появиться
на сцене во время танца. Каждая корова \(i\) планирует танцевать определённое время
\(d(i)\). Изначально коровы \(1 \ldots K\) появляются на сцене и начинают танцевать.
Когда первая из этих коров завершит свой танец, она покидает сцену и корова \(K+1\)
немедленно начинает танцевать и т.д. Поэтому всегда \(K\) коров танцуют, за исключением
последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается,
когда последняя корова завершит свой танец в момент времени \(T\).
Понятно, что чем больше значение \(K\), тем меньше время \(T\). Поскольку шоу не может
длится очень долго, вам на вводе даётся верхняя граница \(T_{max}\), указывающая
максимально возможное значение величины \(T\). Ваша задача - определить минимально
возможное подходящее значение \(K\).
ФОРМАТ ВВОДА (файл cowdance.in):
Первая строка ввода содержит
\(N\) и
\(T_{max}\), где
\(T_{max}\) - целое число, не более
1 000 000.
Следующие \(N\) строк задают длительности танцев \(d(1) \ldots d(N)\) для коров
\(1 \ldots N\). Каждое из \(d(i)\) - целое число в интервале \(1 \ldots 100,000\).
Гарантируется, что если \(K=N\), шоу закончится вовремя.
ФОРМАТ ВЫВОДА (файл cowdance.out):
Выведите наименьшее возможное значение \(K\) такое, что танцевальное шоу
закончится не более чем через \(T_{max}\) единиц времени.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 8
4
7
8
6
4
|
4
|