第一天 0 假设你有日元。
每天 P 您可以获得日元津贴。
几天内总计
我想购买 N 卡。
每日最低卡使用量
您可以购买 0 枚、最大 M 副本。
有一天你 k 枚 (k = 1, 2, ..., M) 购买卡时
x_1 + x_2 + ... + x_k 你必须支付日元。
如果不买票,你的零用钱也不会减少。
x_1 \leq P 有保证。
在
N 求购买一张卡所需的最短天数。
以整数形式打印购买
入力形式
输入按以下格式给出。
N M P x_1 … x_M
出力形式
N 卡所需的最少天数。
制約
- 1 \leq N \leq 100
- 1 \leq M \leq 20
- 1 \leq P \leq 100000
- 1 \leq x_i \leq 100000 (i = 1, 2, ..., M)
- x_1 \leq P
- 所有输入均为整数。
针对该问题的判断设置了一组30分的测试用例。除了上述约束之外,该组中包含的测试用例还满足以下约束。
- x_1 \leq x_2 \leq ... \leq x_M
入出力例
入力例1
9 4 4 1 2 3 4
出力例1
4
例如,如果前三天购买两张卡,则每天需要支付1+2=3日元。 第4天,除了当天收到的4日元外,还可以使用7日元,这样1+2+3=6日元就可以买3张卡,4天就可以买9张卡。
入力例2
8 4 3 3 1 1 1
出力例2
4
此输入示例不满足部分点约束。