очень нужно C. Морозостойкость массива
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
В Межгалактическом исследовательском центре проводят испытания массивов низкими температурами.
Оказалось, что при достаточно низких температурах массивы имеют свойство сжиматься. Сжатие массивов происходит следующим образом: два элемента в начале или в конце массива соединяются в один элемент. Значение полученного элемента равно сумме исходных элементов. Например, массив [7,5,9,8,3] может сжаться до [12,9,8,3] или до [7,5,9,11]. Массив размера 1 не может сжаться.
Также массивы имеют определенную прочность. Прочность массива определяется числом S, означающим наибольшее возможное значение элемента массива. Полученный при сжатии массива элемент не может превышать его прочность, иначе, если размер массива больше 1, то он ломается.
Морозостойкостью массива является число R — максимальная величина, на которую может уменьшиться длина массива, и массив при этом не сломается.
Вычислите морозостойкость для данного массива.
Входные данные
В первой строке заданы два целых числа n и S (1≤n≤2⋅105,1≤S≤109) — соответственно, размер и прочность массива.
Во второй строке заданы n целых чисел a1,a2,…,an (1≤ai≤S) — элементы массива.
Выходные данные
Выведите одно число R — искомую морозостойкость массива.
Система оценки
за каждый тест начисляются независимо.
Примеры
входные данныеСкопировать
5 15
7 5 9 8 3
выходные данныеСкопировать
2
входные данныеСкопировать
5 21
7 5 9 8 3
выходные данныеСкопировать
3
входные данныеСкопировать
5 100
7 5 9 8 3
выходные данныеСкопировать
4
