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
Shubham Jadhav:
20170502 09:47:28
sliding window is the way to go :) 

thefriction:
20170501 15:11:21
Spoj comments are cancer.


vettyvignesh:
20170421 08:58:31
TLE despite going from O(n^2) to O(n). Hopeless. #java 

taran106:
20170402 22:05:29
got ac in O(N). approach was like bruth force but took help of the previous step's sum to optimize the inner loop and made it O(N) :D 

amandal799:
20170329 17:45:34
solved using binary_search AC in one go !! 

k4netmt:
20170328 17:40:06
Who can help me? So, I summit some times but this return time limit exceeded for me. Because, this is my first solution. I have tested with some case as below:


nikhil_ankam:
20170325 10:56:05
Come on SPOJ, tle in java but AC in CPP. So, many times this happened to me. 

sandeep_4141:
20170308 21:56:04
rolling pointer, AC in one go ! :)) 

da_201501181:
20170304 10:15:52
AC in one GO..!! O(N) Two pointers 

nilabja16180:
20170228 09:41:40
AC in ONE GO!!!

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