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
guru_shreyansh:
20210914 11:37:06
Solved this question with both Sliding Window & Binary Search approach. BUT...


Waseem Ahmed:
20210626 21:27:19
Ac in one go. Super simple sliding window (two pointer) problem. 

princeoftime05:
20210228 04:57:04
AC in one go with binary search UwU 

rishikey:
20210226 13:23:54
not an interesting problem.. 

deerawat:
20210103 10:41:52
easy one 

shreyas_07:
20201208 10:52:33
could have also solved using DP if constraints were small. 

varuntumbe:
20201020 08:13:13
beautiful algorithm. creative use of two pointers. 

gnomegeek:
20200814 09:12:05
AC in one go. Basic sliding window problem. 

justrifat:
20200727 21:32:32
AC in one go :)


kumar_anubhav:
20200630 13:59:19
AC in one Go!! 
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 