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
narutohokage_1: 2017-02-03 20:18:56

No searching on google for a algorithm , instead think and you will get one , was getting WA Because was adding sum again in each cycle , please see that you can use previous sum of hotel price , instead of calculating it again from scratch in each cycle.

coder_hsnake: 2017-01-31 01:47:34

ALIENS = CODEFURY =HOTELS-(without considering number of hotels just focus on max sum)
TRY OTHER TWO after trying HOTELS

epsilonalpha: 2017-01-29 17:06:00

A/C in one go! No algorithm needed, simple two pointer technique. :)

hasan356: 2016-12-30 07:53:58

used deque!!

kira28: 2016-12-16 21:42:46

try this->
8 63
8 32 1 5 4 9 12 3
o/p=63

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


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 except: ASM64
Resource:that would be me