HOTELS - Hotels Along the Croatian Coast

no tags 

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

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

hide comments
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

---@@@----: 2015-06-05 05:58:41

Nice question..
Done it using Sliding Window concept... :)

sathya_dev: 2015-05-20 17:51:17

Learnt new way of thinking :)

Vaporeon: 2015-05-19 20:03:45

My dp solution giving WA ar running judge(7)..
My submission id is:14282110
please help :(