Полоска перекусов

После школы Ира каждый день покупает себе небольшой перекус. Она записала, сколько потратила в каждый из n дней подряд.

Ира нашла у себя купон: если выбрать подряд несколько дней, то суммарно за перекусы в эти дни можно потратить не больше L. Ей хочется понять, какая самая длинная «полоска» подряд идущих дней ей подходит.

Нужно вывести максимальное количество подряд идущих дней, суммарные траты за которые не превышают L.

Формат ввода

В первой строке два целых числа n и L. Во второй строке n целых чисел a1, a2, ..., an — траты по дням.

Формат вывода

Одно целое число — максимальная длина подходящей полоски.

Ограничения

• 1 ≤ n ≤ 5000
• 1 ≤ L ≤ 1 000 000
• 1 ≤ ai ≤ 1000

Пример

Ввод:

7 10
2 3 1 2 4 3 2

Вывод:

4

Ключевое наблюдение: все траты ai положительные. Значит, если мы расширяем отрезок вправо, его сумма только растёт, а чтобы снова уложиться в лимит L, достаточно двигать левую границу вправо (сумма будет уменьшаться). Это идеально подходит для приёма «скользящее окно».

Идея: поддерживаем текущий отрезок [l..r] и его сумму s. Для каждого нового r добавляем a[r]. Если сумма стала больше L, сдвигаем l, вычитая элементы, пока снова не станет s <= L. Тогда отрезок [l..r] — самый длинный с данным r, потому что левее уже нельзя (там было бы слишком много).

План:

• Инициализируй l = 0, s = 0, best = 0.
• Для каждого r от 0 до n-1:
• прибавь a[r] к s;
• пока s > L, вычитай a[l] и увеличивай l;
• обнови ответ best = max(best, r - l + 1).
• Выведи best.

Мини-сниппет пересчёта окна: s += a[r]; while s > L: s -= a[l]; l += 1.

Сложность по времени: O(n), потому что каждый указатель проходит массив не больше одного раза.

Частая ошибка: заменять while на if. Сумма может превышать L сильно, и одного сдвига l может не хватить — нужно сдвигать, пока условие не выполнится.