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-04-11 15:50:22 sourav
Easy
2014-04-10 15:10:50 utkarsh agarwal
please provide tricky test cases!
2014-03-17 08:23:37 Innovolt
hahahha.......O(n) ...AC....0.94s
2014-02-17 17:55:39 Dhruv Mullick
A nice and tricky problem. Was making a small mistake which cost me 3 WAs.
2014-02-07 09:59:46 Anmol Pandey
Cherished the moments I used solving this...Great question..
finally AC 0.96sec....but need to improve
2014-02-05 18:32:50 Prahalad
Hey fellow coders i have attempted this problem and got a AC at 0.33 s , i feel my solution is O(n).Kindly have a look at my code at this link http://ideone.com/YKGCJU and suggest changes . thanks :)
2014-01-01 12:18:28 Ankit Jain
just look at the second test case....and code up the thing...very easy prob..
2013-12-31 12:13:00 parbays
Test cases seems not complete. If all the hotels added value is less than the required- the answer shud be the value of all hotels. But solution with value of n-1 hotels is gettting accepted.
2013-12-22 11:46:52 Brute_Force
getting WA in the 7th judge!!Any specific test cases


Last edit: 2013-12-22 11:47:31
2013-12-12 12:44:28 ABHISHEK004
same code accepted in C and TLE in c++...... strange :/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.