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
shahayush457:
20190618 20:38:17
It's easy !!! Binary search and sliding window both solutions are accepted... 

protyush:
20190408 13:27:40
weak test cases 

suraj_13:
20190321 17:11:17
Use sliding window, and a variable max to keep track of best solution 

f23505106:
20190115 08:14:00
any one AC in python? 

yaseenmollik:
20181222 08:23:02
Great use of Two Pointers 

markaman:
20181208 07:10:02
LEARN SW CONCEPT THIS WILL HELP U ;) Last edit: 20181208 07:13:06 

inkretbear:
20180827 10:24:33
Should be stronger restrictions, O(N) solution is easy to both make it up and code it.


fr0zen:
20180813 01:50:51
AC in 2³² go!!! 

masterchef2209:
20180809 14:13:17
AC in 1 go :D 

bartosz_panek:
20180726 18:43:13
Java  time limit exceeded. Same code in c++ and accepted xD 
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 