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 
hide comments
papan_97:
20160416 08:49:45
after a few TLEs,,,finally came up with a O(n) solution X) 

constant_:
20160316 14:29:27
helped to get back on track ;) 

a_b_c12345:
20160204 11:31:22
do not search for any algo on google.. just do it by urself .. AC in 1 go...


nonushikhar:
20160103 16:54:43
O(n) :) 

asshole:
20151223 11:20:47
i think you should change the time limit so that it can be accepted in python too 

sharif ullah:
20151019 11:29:39
modified version of KAdane's algorithm!!! 

Dushyant Singh:
20151006 11:22:01
Weak test cases. One of my AC code gives 10 for first output. 

theweblover007:
20151005 12:31:14
The algorithm behind this is kadane's algorithm, no you dont need to learn it, its very intuitive. 

shshnk28:
20150928 15:19:07
some times the difference between tle and ac could be just changing the language from Python to c++. With the same logic. 

snehil10111995:
20150925 16:51:03
No algo. O(n). :) 
Added by:  Adrian Satja Kurdija 
Date:  20111030 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  that would be me 