装箱 (pack)

题目描述

Alice 喜欢吃零食。她想把零食装到箱子里去。

Alice 现在有 $m$ 个箱子，每个箱子的容积为 $k$。Alice 有 $n$ 份零食，每个零食有占据的体积 $a_i$。Alice 将采取这样的策略装入箱子中：

• 若当前的箱子中剩余的容积可以装入这份零食，将这份零食装入；
• 否则，将零食装入下一个箱子。

显然，Alice 有可能会遇到麻烦：当前的零食已经没有箱子可以装了。所以 Alice 会一开始主动地放弃掉前若干份零食，从第 $c$ 份零食再开始装箱，在此之前的 $c-1$ 份零食全部丢弃，以便使得剩余的零食全部可以装入到箱子之中去。Alice 想要最大化能够装入箱子的零食数量。

你的任务是帮助 Alice 计算她可以装入箱子的最多零食数量。

输入格式

在文件 pack.in 中读入。 第一行三个正整数 $n,m,k$，以空格隔开，分别表示零食份数、箱子数量、每个箱子容积。 接下来一行 $n$ 个空格隔开的正整数，依次表示每份零食的体积。保证零食的体积不会大于单个箱子的容积。

输出格式

在文件 pack.out 中输出。 一行一个正整数，表示 Alice 最多可以向箱子中放入多少零食。

样例

样例输入 #1

5 2 4
1 1 3 2 2

样例输出 #1

4

样例 1 解释： Alice 放弃第一份零食，从第二份开始：第一个箱子装第 2、3 份($1+3=4$)，第二个箱子装第4、5份($2+2=4$)，共4份。

数据范围

共 10 个测试点，每个测试点 10 分。