Silheundeyo

Interview

Time limit1sMemory limit1024 MB

Summary

Given N positive integers, find the largest sum of a contiguous block that does not exceed M.

Level: Medium4 of 10
Topics: Sliding window, Two pointers
Solved: No attempts yet

Problem

The hamster Silheundeyo tries to block the cracked jar with its own body for Kongjwi.

A hamster is a fluid, so it can stretch its body as shown in the picture.

Also, since the hamster is a fluid, it can stretch its body as shown in the picture below.

However, the hamster's volume is fixed at $M$ , so there is a limit to how far it can stretch.

The jar has $N$ holes in a row from the left. The size $A\_i$ of the $i$ -th hole is given. To plug a hole, the hamster must use exactly that much volume.

Silheundeyo wants to help Kongjwi as much as possible, so it wants to use as much of its volume as it can.

Find out how to plug the holes so that the hamster plugs the jar the way it wants, and report it.

Even though a hamster is a fluid, it cannot split its body in two, so all the holes it plugs must be contiguous.

Input

$N$ $M$

$A\_1$ $A\_2$ ... $A\_N$

Output

Print the maximum volume that can be used to plug the holes.

Constraints

$1\leq N\leq 500\,000$
$1\leq M\leq 10^9$
$1\leq A\_i\leq 10^9$

Examples1

Example 1
Input
```
8 10
2 2 2 2 11 2 5 2
```
Expected output
```
9
```