## HOTELS - Hotels Along the Croatian Coast

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`

hide comments
 shahayush457: 2019-06-18 20:38:17 It's easy !!! Binary search and sliding window both solutions are accepted... protyush: 2019-04-08 13:27:40 weak test cases suraj_13: 2019-03-21 17:11:17 Use sliding window, and a variable max to keep track of best solution f23505106: 2019-01-15 08:14:00 any one AC in python? yaseenmollik: 2018-12-22 08:23:02 Great use of Two Pointers markaman: 2018-12-08 07:10:02 LEARN SW CONCEPT THIS WILL HELP U ;) Last edit: 2018-12-08 07:13:06 inkretbear: 2018-08-27 10:24:33 Should be stronger restrictions, O(N) solution is easy to both make it up and code it. Just calculate the maximum for each fixed first position of the interval. fr0zen: 2018-08-13 01:50:51 AC in 2³² go!!! masterchef2209: 2018-08-09 14:13:17 AC in 1 go :D bartosz_panek: 2018-07-26 18:43:13 Java - time limit exceeded. Same code in c++ and accepted xD

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