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 < 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:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:that would be me

hide comments
2021-09-14 11:37:06
Solved this question with both Sliding Window & Binary Search approach. BUT...
Sliding Window in Java and Python got Accepted.
While,
Binary Search in Java and Python (with Fast I/O) gave TLE... and got accepted in C (0.15s).
2021-02-26 13:23:54
not an interesting problem..
2021-01-03 10:41:52
easy one
2020-12-08 10:52:33
could have also solved using DP if constraints were small.
2020-10-20 08:13:13
beautiful algorithm. creative use of two pointers.
2020-06-23 11:08:51
Spoiler:
can be done using Binary search and also by sliding window.
hint:use prefix sums for binary search method and you can use dequeue for sliding window.
I personally learnt a lot from this question.
2020-06-18 19:37:23
can anyone provide binary solution code...
2020-04-08 11:32:55
good question

Last edit: 2020-04-08 11:35:18
2020-01-29 21:57:30
The wrong Solution got AC!
Realized while solving ALIEN.
2019-12-21 12:30:04
How can this problem be done using Binary Search ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.