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
jasbir_220b2: 2016-08-17 12:19:04

O(n) solution.... simple but good one

vaibhav goyal: 2016-08-13 23:54:55

try with binary search too apart from two pointer technique....may be you will learn something as applying usual binary search you may caught in an infinite loop :D

Nallagatla Manikanta: 2016-08-10 14:36:19

O(n) possible :) accepted in one go :)

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++

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

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

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)


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