SPOJ.com - Problem HOTELS

HOTELS - Hotels Along the Croatian Coast

#sliding-window-1

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 < 2³¹).

In the next line there are N natural numbers less than 10⁶, 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

input

4 9
7 3 5 6

output

Submit solution!

hide comments

< Previous 1 2 3 4 5 6 7 8 9 10 11 Next >

	rohit9934: 2017-06-01 17:55:01 Awesome. Learn Two pointer.Brute Force will only show you orange TLE.
	Shubham Jadhav: 2017-05-02 09:47:28 sliding window is the way to go :)
	thefriction: 2017-05-01 15:11:21 Spoj comments are cancer. everybody will be boasting that they got AC in x.y seconds, AC in one go !!!!! and bs++ instead of sharing something valuable. C'mon we are supposed to do better guys.
	vettyvignesh: 2017-04-21 08:58:31 TLE despite going from O(n^2) to O(n). Hopeless. #java
	taran106: 2017-04-02 22:05:29 got ac in O(N). approach was like bruth force but took help of the previous step's sum to optimize the inner loop and made it O(N) :D
	amandal799: 2017-03-29 17:45:34 solved using binary_search AC in one go !!
	k4netmt: 2017-03-28 17:40:06 Who can help me? So, I summit some times but this return time limit exceeded for me. Because, this is my first solution. I have tested with some case as below: 5 12 2 1 3 4 5 --------- 4 9 7 3 5 6 -------- 6 5 6 7 3 1 8 5 ------------- 8 63 8 32 1 5 4 9 12 3 . The result is correct. Thanks for answer
	nikhil_ankam: 2017-03-25 10:56:05 Come on SPOJ, tle in java but AC in CPP. So, many times this happened to me.
	sandeep_4141: 2017-03-08 21:56:04 rolling pointer, AC in one go ! :))
	da_201501181: 2017-03-04 10:15:52 AC in one GO..!! O(N) Two pointers

Submit solution!

Added by:	Adrian Satja Kurdija
Date:	2011-10-30
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	that would be me