J - カード
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
あなたは最初の日に 0 円持っているとする。
毎日 P 円のお小遣いをもらえるので
何日かかけて合計で N 枚のカードを買いたい。
カードは1日に最低 0 枚、最大 M 枚買うことができる。
あなたがある日に k 枚 (k = 1, 2, ..., M) のカードを買う場合には
x_1 + x_2 + ... + x_k 円を支払わなければならない。
1枚も買わない場合には、お小遣いは減らない。
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
例えば、初めの3日間にカードを2枚ずつ買うとすると、1日あたり1+2=3 円支払う。 4日目は、その日にもらえる4円と合わせて7円使うことができるので、1+2+3=6円で3枚のカードを買い、4日で9枚のカードを買うことができる。
入力例2
8 4 3 3 1 1 1
出力例2
4
この入力例は部分点の制約を満たしていない。