K. Kaneiji Meilong Robotics
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Robotics Institute at Carnegie Mellon University has a linear obstacle course of length $$$n$$$. The heights of the obstacles are described by an integer array $$$a$$$, where $$$a_i$$$ denotes the height of the obstacle at location $$$i$$$. In particular, if $$$a_i = 0$$$, then there is no obstacle at location $$$i$$$.

With a budget of $$$d$$$ dollars, SnowballSH can choose a nonnegative integer $$$h_{\mathrm{init}} \le d$$$ and construct a robot of height $$$h_{\mathrm{init}}$$$. Then, his robot will go through the obstacle course in the following manner: for each $$$i=1,2,\dots,n$$$, when the robot encounters an obstacle with value $$$a_i \gt 0$$$, one of the two possibilities happens:

  • If the current height of the robot $$$h$$$ is less than $$$a_i$$$, then nothing happens, since the robot is shorter than the obstacle.
  • If the current height of the robot $$$h$$$ is at least $$$a_i$$$, then the new height changes to $$$h' = h - a_i$$$.

Please help SnowballSH determine the maximum possible height which the robot can end up at after running through the obstacle course over all $$$0 \le h_{\mathrm{init}} \le d$$$.

Input

The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le d \le 10^9$$$) — the length of the obstacle course and SnowballSH's budget, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the description of the obstacle course.

Output

Output a single integer — the answer to the problem.

Examples
Input
5 5
0 2 6 1 3
Output
2
Input
7 10
7 6 2 5 0 1 4
Output
2
Input
11 1000
3 1 4 1 5 9 2 6 5 3 5
Output
956