Competitions
Queue Data Structure
Hotels Along the Croatian Coast
There are n hotels along the beautiful Adriatic coast. Each hotel has its value in Euros.
Peter has won m Euros on the lottery. Now he wants to buy a sequence of consecutive hotels, such that the sum of the values of these consecutive hotels is as great as possible — but not greater than m.
You are to calculate this greatest possible total value.
Input data
In the first line there are integers n and m~(1 \le n \le 3 \cdot 10^5, 1 \le m < 2^{31}). In the next line there are n positive integers less than 10^6, representing the hotel values in the order they lie along the coast.
Output data
Print the required number (it will be greater than 0 in all of the test data).
Examples
Input example #1
5 12 2 1 3 4 5
Output example #1
12