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
amar_shukla1:
20200623 11:08:51
Spoiler:


jojo38:
20200618 19:37:23
can anyone provide binary solution code... 

aman5898:
20200414 20:16:02
Ac in one go :p 

geek_goku6:
20200408 11:32:55
good question Last edit: 20200408 11:35:18 

suyashky:
20200129 21:57:30
The wrong Solution got AC!


bala_24:
20191221 12:30:04
How can this problem be done using Binary Search ? 

akhand_mishra:
20190926 22:16:57
weak test cases my wrong sub. got AC. 

ahzong:
20190814 01:28:52
How to use binary search on this problem? :):) Last edit: 20190814 06:55:45 

medhruv7:
20190723 23:31:06
i dont know how to do with sliding window. Did it easily with binary search


tanaygupta2000:
20190628 11:09:39
AC in 2 go 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 