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 < 2^{31}).
In the next line there are N natural numbers less than 10^{6}, 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
input5 12 2 1 3 4 5output 12 
input4 9 7 3 5 6output 8 
Added by:  Adrian Satja Kurdija 
Date:  20111030 
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
kingston:
20150616 23:02:54
done using variation of KADANAE'S algorithm simple and easy 

Ankush :
20150608 11:46:05
Amazing problem. But time limit is too strict. Got a TLE in Python but an AC in C++14 :D 

@@@:
20150605 05:58:41
Nice question..


sathya_dev:
20150520 17:51:17
Learnt new way of thinking :) 

Vaporeon:
20150519 20:03:45
My dp solution giving WA ar running judge(7)..


pramttl:
20150512 08:48:25
Time limit is too strict. I submitted a O(n) solution in C++14 (memoized, recursive solution) still got TLE. 

Subhashis Bhowmik:
20150512 05:19:56
My Ans is getting WA, Abeer's case worked, but @Riddhi, the output in your test case shud b 23 as my ans is saying. 6+9+8=23


Abeer Khan:
20141207 22:45:55
Try this test case, Thanks to pero.


Riddhi:
20140923 10:37:56
Try this test case:


AC Srinivas:
20120901 17:37:04
similar problem ALIEN 