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 except: SCM chicken
Resource:that would be me

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

pramttl: 2015-05-12 08:48:25

Time limit is too strict. I submitted a O(n) solution in C++14 (memoized, recursive solution) still got TLE.

Subhashis Bhowmik: 2015-05-12 05:19:56

My Ans is getting WA, Abeer's case worked, but @Riddhi, the output in your test case shud b 23 as my ans is saying. 6+9+8=23
EDIT: Sorry, didn't see consecutive, sorted the array first. My bad :p

Last edit: 2015-05-12 05:46:31
Abeer Khan: 2014-12-07 22:45:55

Try this test case, Thanks to pero.
6 12
1 2 3 4 5 1
O/P
12

Riddhi: 2014-09-23 10:37:56

Try this test case:
9 23
2 8 18 9 91 6 4 2 1

Output: 18