Problem Description

E869120 lives in the Takahashi Kingdom.
He works at AtCodeer Corporation, where there is a mandatory meeting that starts every day at time $ 0 $.
The Takahashi Kingdom has $ N $ cities numbered $ 1, 2, 3, ..., N $ from west to east. His home is in city $ 1 $, and his company is in city $ N $. There are bidirectional roads connecting city $ i $ and city $ i+1 $ ($1 \leq i \leq N - 1$), and it takes $ A_i $ units of time to travel on these roads. Note that $ 1 $ unit of time is the time from $ 0 $ to $ 1 $.

One day in 2031, he woke up and checked the clock, only to find it was already time $ 0 $!
If he continues like this, he will be late for the meeting. AtCodeer Corporation is strict about lateness, and even one instance of being late will not be tolerated lightly. He could be fired on the spot!
However, he has a special ability called "Time Leap", which can send him back in time by $ T $ units of time when used once. He can use this ability in any city.

To avoid being late for the meeting, i.e., to arrive at the company in city $ N $ at time $ 0 $ or earlier, how many times does he need to use the "Time Leap" ability at a minimum?
Note that he can start his actions at the time he wakes up, which is time $ 0 $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the minimum number of times the "Time Leap" ability must be used in one line.

Sample Input and Output

Sample Input #1

2 1
3

Sample Output #1

3

Sample Input #2

3 4
5 6

Sample Output #2

3

Notes/Hints

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.

Partial Points

This problem is divided into several sub-tasks, and you are considered to have solved a sub-task if you correctly answer all test cases for that sub-task.
The score of your submitted source code is the sum of the points for the sub-tasks you solved.

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

Sample Explanation 1

For example, by taking the following actions, the number of "Time Leap" uses can be reduced to $ 3 $, which is the minimum. 1. Initially, E869120 is in city $ 1 $ and the time is $ 0 $. 2. Use "Time Leap" $ 3 $ times in city $ 1 $. After this, the time is $ -3 $. 3. Move from city $ 1 $ to city $ 2 $. By the time the move is complete, the time is $ 0 $, and he makes it just in time!

Sample Explanation 2

Note that this input example does not satisfy the constraints of sub-task $ 1 $.

见题面 Input 部分

见题面 Output 部分