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
puneethnaik:
20180213 13:32:38
prefix sum + upper_bound(binary search) did it for me.best of luck for others. 

satyampnc:
20180111 06:46:06
sliding window... ac in 1 go :) 50th


aimbot:
20180109 13:00:19
2 ez 

kmkhan_014:
20171218 18:32:04
beauty!!!


shizukaa:
20171026 17:05:10
Hint on implementation: Use List simply(or you use two pointer but at last you will doing the same thing).


frozen7:
20171013 17:04:53
Can be solved using binary_search in O(nlogn) or using two pointer technique in O(n) Last edit: 20171013 19:00:19 

hitman007:
20170924 20:45:59
I wrote unexpected number of loops and ifelse. Am I doing something wrong ? Although I used sliding window method and AC. 

darkdreamofmy1:
20170905 20:59:42
ac in one go LOL 

jayu_jd:
20170709 16:59:18
Nice problem!


anurag_tangri:
20170705 14:10:48
AC IN ONE GO :) prefix sum and two pointers :D 
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 