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

2016-12-30 07:53:58
used deque!!

2016-12-16 21:42:46
try this->
8 63
8 32 1 5 4 9 12 3
o/p=63

2016-09-21 05:48:40
Thought it was a little annoying dealing with single hotels that might cost more than the cost limit. Try:

6 5
6 7 3 1 8 5

Answer: 5

2016-09-15 17:25:31
Deque ftw :D

2016-08-17 12:19:04
O(n) solution.... simple but good one

2016-08-13 23:54:55 vaibhav goyal
try with binary search too apart from two pointer technique....may be you will learn something as applying usual binary search you may caught in an infinite loop :D

2016-07-04 16:37:39 kartikay singh
try with two pointer techinque

2016-07-03 14:38:04
Yes !!! Solved!! Thanks for the hint @Sourabh Goel

2016-06-19 08:38:16
Done with BinarySearch..
Should try with Sliding Window.

2016-06-17 21:31:35
TLE for O(n^2) in C++