Sphere Online Judge

SPOJ Problem Set (classical)

9861. Hotels Along the Croatian Coast

Problem code: HOTELS


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:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:that would be me

hide comments
2014-10-24 07:49:25 Bejgum Raviteja
O(N).. Don't think complex, one perfect look can solve this.. Nice problem for refreshing :D
2014-10-21 14:07:23 Diksha Jaiswal
took 1 hr...enjoyed solving :)
2014-10-16 12:19:21 esemzV
nice problem,pretty easy, AC in one go, can be done in O(n)
2014-10-08 18:58:35 jetpack
4 WA for overseeing the limits.
2014-09-27 23:34:50 Arun Karthikeyan
O(NlogN) AC
2014-09-26 15:45:12 jack sparrow
o(n) ;)
2014-09-23 10:37:56 Riddhi
Try this test case:
9 23
2 8 18 9 91 6 4 2 1

Output: 18
2014-09-09 19:42:49 Rajat (1307086)
enjoyed a lot while solving this................
those stuck on case seven try dis
7 22
7 5 6 3 1000 11 11

22
happy coding :)
2014-09-09 19:36:30 Rajat (1307086)
enjoyed a lot while solving this................
those stuck on case seven try dis
7 22
7 5 6 3 1000 11 11

22
happy coding :)
2014-08-25 16:11:17 sg
easy one first attempt AC :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.