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
rohit gajawada: 2015-09-24 11:47:21

whats up raghu

gullu_mishra: 2015-09-22 18:55:56

50th in spoj ..AC in 1 go...nice problem

topke: 2015-09-03 20:29:11

There is nothing to memoize here. Solution is O(n) , you don't need any algorithm to solve this one.

swapnil1996: 2015-08-22 09:23:58

Nice problem....

Mohammad Nasirifar: 2015-08-13 15:40:06

AC O(nlg(n)) :D

ROHIT Kumar: 2015-08-11 09:10:27

thnks for the test cases @abeer khan and @ridhi
ac after a lot of tries on ideone

Anurag Sharma: 2015-08-01 08:45:44

ac after lot more troubles.... finally did troubleshooting

Last edit: 2015-08-11 09:11:09
Nitesh Tiwari: 2015-07-23 16:11:15

Do we have to consider negative numbers?

kingston: 2015-06-16 23:02:54

done using variation of KADANAE'S algorithm simple and easy

Ankush : 2015-06-08 11:46:05

Amazing problem. But time limit is too strict. Got a TLE in Python but an AC in C++14 :D


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