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
deerawat: 2021-01-03 10:41:52

easy one

shreyas_07: 2020-12-08 10:52:33

could have also solved using DP if constraints were small.

varuntumbe: 2020-10-20 08:13:13

beautiful algorithm. creative use of two pointers.

gnomegeek: 2020-08-14 09:12:05

AC in one go. Basic sliding window problem.

justrifat: 2020-07-27 21:32:32

AC in one go :)
#using_two_pointer ^_^

kumar_anubhav: 2020-06-30 13:59:19

AC in one Go!!

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

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