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
davidgalehouse: 2016-09-21 05:48:40

Thought it was a little annoying dealing with single hotels that might cost more than the cost limit. Try:

6 5
6 7 3 1 8 5

Answer: 5

akshayvenkat: 2016-09-15 17:25:31

Deque ftw :D

Shantanu Banerjee: 2016-09-14 18:37:09

simple O(N). AC in one go! :)

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


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