D. Упаковывание в коробки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Максима есть $$$n$$$ предметов и $$$m$$$ коробок, каждая коробка имеет размер $$$k$$$. Предметы пронумерованы от $$$1$$$ до $$$n$$$ в порядке слева направо, размер $$$i$$$-го предмета равен $$$a_i$$$.

Максим хочет упаковать предметы в коробки и он собирается упаковывать предметы по следующему алгоритму: он берет одну из пустых коробок, которые у него имеются, идет слева направо по предметам, которые у него есть, и если $$$i$$$-й предмет помещается в текущую коробку (оставшийся размер коробки больше либо равен $$$a_i$$$), он кладет его в эту коробку и оставшийся размер коробки уменьшается на $$$a_i$$$. Иначе он берет новую коробку и продолжает процесс, описанный выше. Если у него не остается пустых коробок и есть еще хотя бы один предмет, который не упакован в коробку, то Максим не может упаковать выбранный набор предметов.

Максим хочет знать максимальное количество предметов, которые он может упаковать при помощи алгоритма, описанного выше. Чтобы достичь цели, он будет выбрасывать самый левый предмет из набора до тех пор, пока оставшийся набор предметов не сможет быть упакован в коробки, которые у него имеются. Ваша задача — найти максимальное количество предметов, которые Максим сможет упаковать в коробки, которые у него имеются.

Каждый раз, когда Максим пытается упаковать предметы в коробки, сначала он опустошает все коробки, которые у него есть (и относительный порядок оставшегося набора предметов не меняется).

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

Первая строка входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — количество предметов, количество коробок и размер каждой коробки.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le k$$$), где $$$a_i$$$ равно размеру $$$i$$$-го предмета.

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

Выведите максимальное количество предметов, которые сможет упаковать Максим при помощи алгоритма, описанного в условии задачи.

Примеры
Входные данные
5 2 6
5 2 1 4 2
Выходные данные
4
Входные данные
5 1 4
4 2 3 4 1
Выходные данные
1
Входные данные
5 3 3
1 2 3 1 1
Выходные данные
5
Примечание

В первом тестовом примере Максим может упаковать только $$$4$$$ предмета. Сначала он пытается упаковать все $$$5$$$ предметов. Распределение предметов будет выглядеть как $$$[5], [2, 1]$$$. Максим не может упаковать следующий предмет во вторую коробку и пустых коробок у него не осталось. Затем он выбрасывает первый предмет и распределение предметов будет выглядеть как $$$[2, 1], [4, 2]$$$. Таким образом, ответ равен $$$4$$$.

Во втором тестовом примере очевидно ,что Максим не может упаковать предметы, начиная с первого, второго, третьего и четвертого (во всех этих случаях распределение предметов выглядит как $$$[4]$$$), но он может упаковать последний предмет ($$$[1]$$$).

В третьем тестовом примере Максим может упаковать все предметы, которые у него есть. Распределение предметов будет выглядеть как $$$[1, 2], [3], [1, 1]$$$.