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
baadshah_: 2016-07-12 16:31:00

AC in one Go!!

Last edit: 2016-07-12 17:55:44
atuldo: 2016-07-05 21:49:43

why the fuck do you guys post hints...

sarvesh_19: 2016-07-05 13:57:45

@Sourabh remove your comment.This is the only trick in this q.

kartikay singh: 2016-07-04 16:37:39

try with two pointer techinque

sonali9696: 2016-07-03 14:38:04

Yes !!! Solved!! Thanks for the hint @Sourabh Goel

pvsmpraveen: 2016-06-19 08:38:16

Done with BinarySearch..
Should try with Sliding Window.

at0000001: 2016-06-17 21:31:35

TLE for O(n^2) in C++

Sourabh Goel: 2016-06-16 09:29:39

very good question O(n) solution Hint: subtract element if sum exceeds the given sum.

aloochaat1998: 2016-06-16 07:23:41

Both for (no. of hotels<=m) and (no. of hotels<m) the solution gets AC :P

kavyasahai: 2016-05-26 20:03:52

TLE :'(


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