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
nilabja16180:
20170228 09:41:40
AC in ONE GO!!!


narutohokage_1:
20170203 20:18:56
No searching on google for a algorithm , instead think and you will get one , was getting WA Because was adding sum again in each cycle , please see that you can use previous sum of hotel price , instead of calculating it again from scratch in each cycle. 

coder_hsnake:
20170131 01:47:34
ALIENS = CODEFURY =HOTELS(without considering number of hotels just focus on max sum)


epsilonalpha:
20170129 17:06:00
A/C in one go! No algorithm needed, simple two pointer technique. :) 

hasan356:
20161230 07:53:58
used deque!! 

kira28:
20161216 21:42:46
try this>


davidgalehouse:
20160921 05:48:40
Thought it was a little annoying dealing with single hotels that might cost more than the cost limit. Try:


akshayvenkat:
20160915 17:25:31
Deque ftw :D 

Shantanu Banerjee:
20160914 18:37:09
simple O(N). AC in one go! :) 

jasbir_220b2:
20160817 12:19:04
O(n) solution.... simple but good one 
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 