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 < 231).

In the next line there are N natural numbers less than 106, 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

input
5 12
2 1 3 4 5
output
12
input
4 9
7 3 5 6
output
8

hide comments
captaindavinci: 2018-06-11 19:01:42

you could also use a deque here.

vivek_dwivedi: 2018-05-26 02:54:10

AC in one go ;) 0.03 sec no idea what sliding window is ..

a161112225: 2018-05-11 13:04:59

this is my 50'th

sohailwiiierd: 2018-03-30 20:59:21

O(N) solution but my time is 0.16sec. How to get 0.00 ??? Give me some hint .

imkiller: 2018-03-19 19:05:08

Codes of 15 lines in cpp using SlidingWindow .
BestOfLuckForOthers.

puneethnaik: 2018-02-13 13:32:38

prefix sum + upper_bound(binary search) did it for me.best of luck for others.

satyampnc: 2018-01-11 06:46:06

sliding window... ac in 1 go :) 50th

aimbot: 2018-01-09 13:00:19

2 ez

kmkhan_014: 2017-12-18 18:32:04

beauty!!!

shizukaa: 2017-10-26 17:05:10

Hint on implementation: Use List simply(or you use two pointer but at last you will doing the same thing).
Hint on logic: it is like putting things in list from back and then removing it from front if your addition of elements gets greater than 'M'. I hope you don't get struck. Happy coding :)


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