For a long time, Anita has been fascinated by arrays. In particular, she is interested in arrays containing natural numbers. After some thinking, she comes to her friend Jacob with the following problem:

You are given an array \(A\) of \(N\) positive integers and a positive integer \(X\). Suppose that \(S\) is the set of subarray sums among all subarrays of the array. Output the maximum element in \(S\) that is less than or equal to \(X\).

Not wanting to tell Anita that he don't know how to solve it, Jacob tells her that he'll have the answer by tomorrow. However, Jacob only knows how to farm and doesn't have a clue how to solve it. He then calls you, his only friend, to bail him out. Can you help Jacob?

Input

The first line consists of two space separated integers, \(N\) and \(X\), denoting the length of the array and the sum that must not be surpassed, respectively.

The next line consists of \(N\) space separated positive integers, representing the \(N\) elements of the array.

Output

Output a single integer representing the maximum subarray sum that is less than or equal to \(X\). In the case that no such subarray exists, output \(-1\).

Subtasks

Over all subtasks,

\(1 \le A_{i} \le 10^{9}\)

\(1 \le X \le 10^{18}\)

Subtask 1 [30%]

\(1 \le N \le 10^{3}\)

Subtask 2 [70%]

\(1 \le N \le 10^{6}\)

Sample Input 1

3 10
1 2 9

Sample Output 1

9

Explanation for Sample Output 1

The set of subarray sums \(S\) is \(\{1,3,12,2,11,9\}\). Among all these values, the largest value less than \(X=10\) is \(9\). Thus, we output \(9\).