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
baadshah_:
20160712 16:31:00
AC in one Go!! Last edit: 20160712 17:55:44 

atuldo:
20160705 21:49:43
why the fuck do you guys post hints... 

sarvesh_19:
20160705 13:57:45
@Sourabh remove your comment.This is the only trick in this q. 

kartikay singh:
20160704 16:37:39
try with two pointer techinque 

sonali9696:
20160703 14:38:04
Yes !!! Solved!! Thanks for the hint @Sourabh Goel 

pvsmpraveen:
20160619 08:38:16
Done with BinarySearch..


at0000001:
20160617 21:31:35
TLE for O(n^2) in C++ 

Sourabh Goel:
20160616 09:29:39
very good question O(n) solution Hint: subtract element if sum exceeds the given sum. 

aloochaat1998:
20160616 07:23:41
Both for (no. of hotels<=m) and (no. of hotels<m) the solution gets AC :P 

kavyasahai:
20160526 20:03:52
TLE :'(

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