Competitions

# Queue Data Structure

# Hotels Along the Croatian Coast

There are n hotels along the beautiful Adriatic coast. Each hotel has its value in Euros.

Peter 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 data

In the first line there are integers n and m (1 ≤ n ≤ 300 000, 1 ≤ m < `2^31`

). In the next line there are n positive integers less than `10^6`

, representing the hotel values in the order they lie along the coast.

## Output data

Print the required number (it will be greater than 0 in all of the test data).

## Examples

Input example #1

5 12 2 1 3 4 5

Output example #1

12