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
akhand_mishra: 2019-09-26 22:16:57

weak test cases my wrong sub. got AC.

ahzong: 2019-08-14 01:28:52

How to use binary search on this problem? :):)

Last edit: 2019-08-14 06:55:45
medhruv7: 2019-07-23 23:31:06

i dont know how to do with sliding window. Did it easily with binary search
AC in one go :)

Last edit: 2019-07-23 23:31:24
tanaygupta2000: 2019-06-28 11:09:39

AC in 2 go xD

shahayush457: 2019-06-18 20:38:17

It's easy !!! Binary search and sliding window both solutions are accepted...

protyush: 2019-04-08 13:27:40

weak test cases

suraj_13: 2019-03-21 17:11:17

Use sliding window, and a variable max to keep track of best solution

f23505106: 2019-01-15 08:14:00

any one AC in python?

yaseenmollik: 2018-12-22 08:23:02

Great use of Two Pointers

markaman: 2018-12-08 07:10:02

LEARN SW CONCEPT THIS WILL HELP U ;)

Last edit: 2018-12-08 07:13:06

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