Sled

Interview

Time limit1sMemory limit1024 MB

Summary

Simulate a sled whose speed changes by a_i on each segment and drops by 1 at junctions whenever it exceeds S; report the final speed.

Level: Easy3 of 10
Topics: Simulation, Implementation, Array
Solved: No attempts yet

Statement

A dwarf loves sledding down a hill along a toboggan track. At the moment he sets off (the very start), the sled's speed is 0. The track is divided into $N$ segments, and for each segment you are told how the sled's speed changes after passing it: it increases or decreases by $a_i$ m/s.

The dwarf's sled is smart — it measures its speed and slows itself down when necessary. If, at the junction between two segments, the sled's speed exceeds $S$ m/s, the sled brakes and its speed decreases by 1 m/s. Braking happens only at junctions between segments, never at the very end of the track.

Determine the speed at which the sled reaches the bottom of the hill (after passing the last segment).

Input

The first line contains the number of segments $N$ and the threshold speed $S$ . Whenever the speed exceeds $S$ , the sled is braked.

Each of the next $N$ lines contains a single integer $a_i$ — how much the sled's speed changes after passing the corresponding segment.

Output

Output the sled's speed at the end of the track.

The input is always such that the sled is guaranteed to finish the whole track, i.e. the speed never drops to 0 (except possibly at the very end of the track).

Constraints

$2 \le N, S \le 1000$
$-10 \le a_i \le 10$

Examples2

Example 1
Input
```
3 4
8
-3
5
```
Expected output
```
9
```
Example 2
Input
```
2 2
2
1
```
Expected output
```
3
```