← 返回题目列表

AtCoder · kupc2014_j

J. 卡

中文机器翻译题面 查看原题

第一天 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

此输入示例不满足部分点约束。