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
jayu_jd: 2017-07-09 16:59:18

Nice problem!
AC in one go.

anurag_tangri: 2017-07-05 14:10:48

AC IN ONE GO :) prefix sum and two pointers :D

shauryauppal: 2017-07-05 13:43:38

Deque concept O(N) answer

9 63
8 32 1 5 4 9 20 12 30

ans->62

babur: 2017-06-24 06:46:17

CAKE WALK

rohit9934: 2017-06-01 17:55:01

Awesome. Learn Two pointer.Brute Force will only show you orange TLE.

Shubham Jadhav: 2017-05-02 09:47:28

sliding window is the way to go :)

thefriction: 2017-05-01 15:11:21

Spoj comments are cancer.
everybody will be boasting that they got AC in x.y seconds, AC in one go !!!!! and bs++
instead of sharing something valuable.
C'mon we are supposed to do better guys.

vettyvignesh: 2017-04-21 08:58:31

TLE despite going from O(n^2) to O(n). Hopeless. #java

taran106: 2017-04-02 22:05:29

got ac in O(N). approach was like bruth force but took help of the previous step's sum to optimize the inner loop and made it O(N) :D

amandal799: 2017-03-29 17:45:34

solved using binary_search AC in one go !!


Added by:Adrian Satja Kurdija
Date:2011-10-30
Time limit:0.184s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:that would be me