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-06-26 21:27:19 Waseem Ahmed
Ac in one go. Super simple sliding window (two pointer) problem.
2021-02-28 04:57:04
AC in one go with binary search UwU
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-08-14 09:12:05
AC in one go. Basic sliding window problem.
2020-07-27 21:32:32
AC in one go :)
#using_two_pointer ^_^
2020-06-30 13:59:19
AC in one Go!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.