Yiit is on a mission to cross the ravine where the treasure lies on the other side. However, the only way to get across is to build a bridge. Yiit comes to you with a bridge idea he prepared in advance, but this bridge is not yet safe enough to cross. Your task is to help Yiit build the bridge while spending the minimum amount of money and also ensuring its safety.

The bridge is divided into N sections, and the inner stress of each section is represented by an array of integers, where each element can range from \(\mathbf{-10^9}\) to \(\mathbf{10^9}\). A negative value indicates that balloons are already tied to that section, reducing its stress, while a positive value indicates the stress level on that part of the bridge.

Yiit can tie a balloon to All of the sections of that bridge for 1 dollar, which decreases the stress of all sections by 1 (thus, affecting the array's elements). However, to ensure the bridge's safety, no interval ([left, right]) on the bridge, when summed, should exceed the limit W.

Determine the minimum amount of money Yiit needs to spend on balloons to ensure that he can safely cross the bridge.

If Yiit can cross the bridge without spending any money, print 0.

Input:

• The first line contains two integers, N, and W, where N is the number of sections of the bridge, and W is the maximum allowed stress on any interval of the bridge.
• The second line contains N integers, representing the initial stress values of each section of the bridge.

Output:

Print a single integer representing the minimum amount of money Yiit needs to spend to make the bridge safe to cross.

Constraints:

• \(1 \leq N \leq 10^5\)
• \(1 \leq W \leq 10^9\)
• Initial stress values of the bridge sections are integers between \(\mathbf{-10^9}\) and \(\mathbf{10^9}\).

Examples

Input 1:

5 5
2 -1 4 1 3

Output 1:

1

Input 2:

5 2
2 -1 4 1 3

Output 2:

2

Explanations

Input 1

In this example, Yiit spends only 1 dollar to tie balloons to all sections, reducing each sections stress level by one, resulting in the stress levels represented by the array [1, -2, 3, 0, 2]. This ensures no interval sum exceeds the limit of 5, allowing Yiit to safely cross the bridge.

Input 2

In this example, Yiit spends 2 dollars this time to tie balloons to all sections, reducing each sections stress level by two, resulting in the stress levels represented by the array [0, -3, 2, -1, 1]. This ensures no interval sum exceeds the limit of 2, allowing Yiit to safely cross the bridge.