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
amar_shukla1: 2020-06-23 11:08:51

Spoiler:
can be done using Binary search and also by sliding window.
hint:use prefix sums for binary search method and you can use dequeue for sliding window.
I personally learnt a lot from this question.

jojo38: 2020-06-18 19:37:23

can anyone provide binary solution code...

aman5898: 2020-04-14 20:16:02

Ac in one go :p

geek_goku6: 2020-04-08 11:32:55

good question

Last edit: 2020-04-08 11:35:18
suyashky: 2020-01-29 21:57:30

The wrong Solution got AC!
Realized while solving ALIEN.

bala_24: 2019-12-21 12:30:04

How can this problem be done using Binary Search ?

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


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