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
hareesh: 2016-04-29 12:11:07

got 1 TLE for O(n^2)
O(n) AC

Irfan: 2016-04-28 09:43:01

solvable with prefix sum .. O(nlogn)

thaihoc06: 2016-04-21 11:01:24

O(n) solution. TLE in Java but got AC in C

papan_97: 2016-04-16 08:49:45

after a few TLEs,,,finally came up with a O(n) solution X)

constant_: 2016-03-16 14:29:27

helped to get back on track ;)

a_b_c12345: 2016-02-04 11:31:22

do not search for any algo on google.. just do it by urself .. AC in 1 go...

nonushikhar: 2016-01-03 16:54:43

O(n) :)

mim16: 2016-01-02 14:40:14

Last edit: 2016-01-02 14:41:08
asshole: 2015-12-23 11:20:47

i think you should change the time limit so that it can be accepted in python too

sharif ullah: 2015-10-19 11:29:39

modified version of KAdane's algorithm!!!


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
Resource:that would be me