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-12-19 05:47:50 abhinav
I got AC in 0.85 with O(n) time comlexity and only 1 for loop (c lang).
Best is <= 0.08 (again c lang)
HOW ?


Last edit: 2014-12-20 07:16:03
2014-12-18 19:34:01 Imtiaz
plz help me got TLE
my code : http://ideone.com/ybibNv
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-12-07 16:17:06 Abeer Khan
Getting WA at test case 7 now! :/ Any ideas? Code works for all test cases posted here
2014-12-05 12:20:58 Abeer Khan
Do we need a new line after printing output?
Getting WA at test case 6!
2014-11-27 04:51:25 Madhur Bhargava
Nice Logic. Fastest IO needed in Java.
2014-11-25 18:34:48 Nandan Mankad
O(n) indeed! Good one!
2014-10-24 19:11:49 appy
running judge (6) is giving tle by using dp...can somebody tell me how to do in O(n) time ..
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 :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.