SPOJ.com - Problem HOTELS

HOTELS - Hotels Along the Croatian Coast

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!

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

hide comments

2018-01-09 13:00:19
2 ez

2017-12-18 18:32:04
beauty!!!

2017-10-26 17:05:10
Hint on implementation: Use List simply(or you use two pointer but at last you will doing the same thing).
Hint on logic: it is like putting things in list from back and then removing it from front if your addition of elements gets greater than 'M'. I hope you don't get struck. Happy coding :)

2017-10-13 17:04:53
Can be solved using binary_search in O(nlogn) or using two pointer technique in O(n)

Last edit: 2017-10-13 19:00:19

2017-09-24 20:45:59
I wrote unexpected number of loops and if-else. Am I doing something wrong ? Although I used sliding window method and AC.

2017-09-05 20:59:42
ac in one go LOL

2017-07-09 16:59:18
Nice problem!
AC in one go.

2017-07-05 14:10:48
AC IN ONE GO :) prefix sum and two pointers :D

2017-07-05 13:43:38
Deque concept O(N) answer

9 63
8 32 1 5 4 9 20 12 30

ans->62

2017-06-24 06:46:17
CAKE WALK