A - E869120, who Leaps through Time Editorial /

Time Limit: 1 sec / Memory Limit: 976 MB

配点：200 点

問題文

E869120 君は、高橋王国に住んでいます。
彼は、AtCodeer 株式会社で働いています。この会社では、毎日時刻 0 に必ず出席しなければならない会議が始まります。
高橋王国には N 個の都市があり、西から順に都市 1, 2, 3, ..., N と番号付けられています。彼の家は都市 1 であり、彼の会社は都市 N です。また 高橋王国には都市 i と i+1 (1 \leq i \leq N - 1) を双方向に結ぶ道路があり、この道路で移動するのに A_i 単位時間かかります。ただし、1 単位時間は時刻 0 から 1 までの時間とします。

2031 年のある日の事です…　彼は起きて時計を確認したら、なんと時刻 0 でした！
このままだと会議に遅れてしまいます。AtCodeer 株式会社は遅刻に厳しいので、会議に一回でも遅れると、叱責・減給どころでは済みません。一発で解雇になってしまいます！
しかし、彼は特殊能力を持っています。これは「タイムリープ」であり、この能力を 1 回使うと時刻が T 単位時間戻されます。「タイムリープ」はいずれかの都市にいるときに使うことができます。

会議に遅刻しないようにする、すなわち都市 N にある会社に時刻 0 またはそれ以前に到着するためには、最低何回の「タイムリープ」を使う必要があるか、求めてください。
ただし、彼は起きた時刻 0 に行動を開始することが出来るとします。

制約

  • N は 2 以上 100 以下の整数
  • T は 1 以上 100 以下の整数
  • A_i は 1 以上 100 以下の整数

部分点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

  1. (100 点)：N = 2, T = 1
  2. (100 点)：追加の制約はない

入力

入力は以下の形式で標準入力から与えられます。 

N T
A_1 A_2 A_3 ... A_{N - 1}

出力

使わなければならない「タイムリープ」の最小回数を、1 行で出力してください。

入力例 1

2 1
3

出力例 1

3

例えば、次のような行動をとると、「タイムリープ」の回数を 3 回にでき、これが最小です。

  1. 最初、E869120 君は都市 1 におり、時刻は 0 である。

  2. 都市 1 で「タイムリープ」を 3 回使う。これが終わった時点で、時刻は -3 である。

  3. 都市 1 から都市 2 に移動する。移動し終わった時点で、時刻は 0 なので、なんと間に合っている！

入力例 2

3 4
5 6

出力例 2

3

この入力例が、小課題 1 の制約を満たさないことに注意してください。

Max Score：200 points

Problem Statement

Mr.E869120 lives in Takahashi Kingdom.
He works as a programmer in AtCodeer Inc, which there is a meeting that we must attend. The meeting is held every day at time 0.
In Takahashi kingdom, there are N cities, and they are called city 1, city 2, city 3, ..., city N from west to east. In addition, there is a road which connects between city i and city i+1 (1 \leq i \leq N - 1), and takes A_i minutes to move.

Something happened on a day of May 2031... He woke up and looked a watch - it was actually time 0, which is the meeting time!
He is going to be late for the meeting. Since AtCodeer Inc. is very strict for being late, he is very likely to be fired!

But he is able to use a magic: TIMELEAP. When he use it, the time will be back by T minutes. He can use TIMELEAP when he is in any city. For example, if T = 3 and he use TIMELEAP at time 8, then the time will be back to 5.
He want to minimize the number of use of TIMELEAP. To not be late for the meeting, how many TIMELEAP should he use?

Constraints

  • N is an integer between 2 and 100 (inclusive)
  • T is an integer between 1 and 100 (inclusive)
  • A_i is an integer between 1 and 100 (inclusive)

Subtasks

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

  1. (100 points)：N = 2, T = 1
  2. (100 points)：No additional constraints.

Input

Input is given from Standard Input in the following format: 

N T
A_1 A_2 A_3 ... A_{N - 1}

Output

Print the minimum number of TIMELEAP that Mr.E869120 should use.

Sample Input 1

2 1
3

Sample Output 1

3

For example, if he does following move, the number of TIMELEAP will be 3.

  1. Initially, Mr.E869120 is in city 1 and the time is 0.

  2. Use TIMELEAP 3 times when he is in city 1. Now the time is -3.

  3. Move from city 1 to city 2. Since it takes 3 minutes, now the time is 0. Note: It is allowed to arrive at city N at time 0.

Sample Input 2

3 4
5 6

Sample Output 2

3

Note this testcase is not included in Subtask 1.