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: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
2014-12-28 10:44:47 Shivi
Finally got AC in 0.82 sec in C lang
2014-12-28 07:24:33 Shivi
http://ideone.com/xE44FS
Gives tle at 7th test case. Please help!!!!

Reply (numerix): If you need help, use the SPOJ forum.

Last edit: 2014-12-28 08:18:54
2014-12-07 22:45:55 Abeer Khan
Try this test case, Thanks to pero.
6 12
1 2 3 4 5 1
O/P
12
2014-09-23 10:37:56 Riddhi
Try this test case:
9 23
2 8 18 9 91 6 4 2 1

Output: 18
2012-09-01 17:37:04 AC Srinivas
similar problem ALIEN
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.