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-08-25 16:11:17 shubham
easy one first attempt AC :)
2014-06-23 12:14:47 Aditya jain
very nice question learned a lot..

2014-06-11 14:51:38 Prakhar Gupta
yeahhh... my 100th on spoj :D
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-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-11-08 09:37:13 sobriquet
nlgn also does the work.
2013-08-13 22:17:28 Rana Saha
Enjoyed Solving this..! Wonderful problem!! :)
2013-08-02 14:53:50 ROHIT KUMAR
easy 1.....
no xtra array needed :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.