题目描述

区块链是由一个个区块构成的，每个区块可以写入不超过 $c$ 个单位长度的数据。如今，需要写入区块链的数据共有 $n$ 项，其中第 $i$ 项数据的长度为 $t_i$ 个单位长度。

小爱只能有 $k$ 个区块可以填写数据，请问她应该选择哪些数据装入区块，才能使写入区块链的数据达到最多？

每份数据必须完整出现在一个区块里，此外，数据有前后关系，比如按照给定的顺序写入区块，不能将编号靠后的数据写到更早的区块里。

输入格式

• 第一行：三个整数： $n$，$c$ 与 $k$；
• 第二行：$n$ 个整数表示 $t_1$ 到 $t_n$。

输出格式

• 单个整数：表示可以写入区块的最大数据条数。

4 5 2
4 3 4 2

3

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$，
• 对于 $60\%$ 的数据，$1\leq n\leq 100$，$1\leq c\leq 100$
• 对于 $100\%$ 的数据，$1\leq k\leq n\leq 1000$， $1\leq t_i\leq c\leq 10000$