CF1066D.Boxes Packing

Maksim has $n$ objects and $m$ boxes, each box has size exactly $k$. Objects are numbered from $1$ to $n$ in order from left to right, the size of the $i$-th object is $a_i$.

Maksim wants to pack his objects into the boxes and he will pack objects by the following algorithm: he takes one of the empty boxes he has, goes from left to right through the objects, and if the $i$-th object fits in the current box (the remaining size of the box is greater than or equal to $a_i$), he puts it in the box, and the remaining size of the box decreases by $a_i$. Otherwise he takes the new empty box and continues the process above. If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects.

Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has.

Each time when Maksim tries to pack the objects into the boxes, he will make empty all the boxes he has before do it (and the relative order of the remaining set of objects will not change).

马克西姆有 $n$ 个物品和 $m$ 个箱子，每个箱子的容量恰好为 $k$。物品从左到右依次编号为 $1$ 到 $n$，第 $i$ 个物品的大小为 $a_i$。

马克西姆希望将这些物品装入箱子中，并采用如下装箱算法：他取一个空箱子，然后从左到右依次检查物品；若第 $i$ 个物品能放入当前箱子（即箱子剩余容量 $\ge a_i$），则将其装入该箱子，箱子剩余容量减少 $a_i$；否则，他取一个新的空箱子，并继续上述过程。如果他已无空箱子可用，但仍有至少一个物品未被装入任何箱子，则马克西姆无法将当前选定的物品集合全部装箱。

马克西姆希望知道：通过上述算法，他最多能装入多少个物品？为达到这一目标，他将不断从当前物品集合的最左侧移除一个物品，直到剩余的物品集合能够被他所拥有的箱子全部装下。你的任务是求出马克西姆最多能装入箱子的物品数量。

每次马克西姆尝试将物品装入箱子前，他都会清空所有箱子（剩余物品的相对顺序保持不变）。

The first line of the input contains three integers $n$, $m$, $k$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le k \le 10^9$) — the number of objects, the number of boxes and the size of each box.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), where $a_i$ is the size of the $i$-th object.

输入的第一行包含三个整数 $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$ 个物体的大小。

Print the maximum number of objects Maksim can pack using the algorithm described in the problem statement.

输出 Maksim 使用题目描述中的算法所能打包的物体的最大数量。

In the first example Maksim can pack only $4$ objects. Firstly, he tries to pack all the $5$ objects. Distribution of objects will be $[5], [2, 1]$. Maxim cannot pack the next object in the second box and he has no more empty boxes at all. Next he will throw out the first object and the objects distribution will be $[2, 1], [4, 2]$. So the answer is $4$.

In the second example it is obvious that Maksim cannot pack all the objects starting from first, second, third and fourth (in all these cases the distribution of objects is $[4]$), but he can pack the last object ($[1]$).

In the third example Maksim can pack all the objects he has. The distribution will be $[1, 2], [3], [1, 1]$.

在第一个例子中，马克西姆最多只能装下 $4$ 个物品。首先，他尝试装下全部 $5$ 个物品，此时物品分配为 $[5], [2, 1]$。马克西姆无法将下一个物品放入第二个箱子，且已没有空余的箱子。接着，他丢弃第一个物品，此时物品分配变为 $[2, 1], [4, 2]$。因此答案为 $4$。

在第二个例子中，显然马克西姆无法从第一个、第二个、第三个或第四个物品开始装下全部物品（在所有这些情况下，物品分配均为 $[4]$），但他可以单独装下最后一个物品（$[1]$）。

在第三个例子中，马克西姆能够装下他拥有的全部物品，物品分配为 $[1, 2], [3], [1, 1]$。