HOTELS - Hotels Along the Croatian Coast

no tags 

There are N hotels along the beautiful Adriatic coast. Each hotel has its value in Euros.

Sroljo 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

In the first line of the input there are integers N and M (1 ≤ N ≤ 300 000, 1 ≤ M < 231).

In the next line there are N natural numbers less than 106, representing the hotel values in the order they lie along the coast.

Output

Print the required number (it will be greater than 0 in all of the test data).

Example

input
5 12
2 1 3 4 5
output
12
input
4 9
7 3 5 6
output
8

Added by:Adrian Satja Kurdija
Date:2011-10-30
Time limit:0.184s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel Pentium G860 3GHz)
Languages:All except: SCM chicken
Resource:that would be me

hide comments
Abeer Khan: 2014-12-07 22:45:55

Try this test case, Thanks to pero.
6 12
1 2 3 4 5 1
O/P
12

Riddhi: 2014-09-23 10:37:56

Try this test case:
9 23
2 8 18 9 91 6 4 2 1

Output: 18

AC Srinivas: 2012-09-01 17:37:04

similar problem ALIEN