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

hide comments
guru_shreyansh: 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).

Waseem Ahmed: 2021-06-26 21:27:19

Ac in one go. Super simple sliding window (two pointer) problem.

princeoftime05: 2021-02-28 04:57:04

AC in one go with binary search UwU

rishikey: 2021-02-26 13:23:54

not an interesting problem..

deerawat: 2021-01-03 10:41:52

easy one

shreyas_07: 2020-12-08 10:52:33

could have also solved using DP if constraints were small.

varuntumbe: 2020-10-20 08:13:13

beautiful algorithm. creative use of two pointers.

gnomegeek: 2020-08-14 09:12:05

AC in one go. Basic sliding window problem.

justrifat: 2020-07-27 21:32:32

AC in one go :)
#using_two_pointer ^_^

kumar_anubhav: 2020-06-30 13:59:19

AC in one Go!!


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