Adam is traveling in a rather narrow city, which can be viewed as a number line. There are $n$ restaurants on the axis, where the $i$-th restaurant ($0 \le i \le n-1$) is located at position $i+1$. Adam starts at $0$ and wishes to eat as much as possible before returning to $0$.

Adam starts with a weight of $1$. We assume his weight increases by exactly the amount he consumes. That is, after eating $a$ units of food, his weight increases by $a$.

To move along the number line, Adam needs energy. Adam starts with $x$ energy, and for every unit of distance he moves, he must spend an amount of energy equal to his current weight. Adam cannot have negative energy at any time. In other words, once Adam's energy is exhausted, he can no longer move.

If Adam is at an integer position $i$ in $[1, n]$ and he has not previously entered restaurant $i-1$, he can enter it and eat exactly $a_{i-1}$ units of food. Adam is a good person and does not waste food.

You must ensure that Adam can return to the starting point $0$. Subject to this, Adam wants to know the maximum total amount of food he can eat.

Implementation Details

You should include city.h and implement the following procedure:

int eat(int n, int x, int[] a)

• $n$: The number of restaurants.
• $x$: The initial energy.
• $a$: An array of length $n$ containing the amount of food obtained by eating at each restaurant in order.
• The procedure you implement will be called exactly once.
• You should return the maximum total amount of food Adam can eat.

Examples

Input 1

5 10
1 1 1 1 1

Output 1

2

Note

It can be proven that in this scenario, Adam can eat at most $2$ units of food, so a correct program should return $2$.

One possible strategy is: walk from $0$ to $1$, spending $1$ unit of energy; enter restaurant $1$ to eat, weight becomes $2$; walk from $1$ to $2$, spending $2$ units of energy; enter restaurant $2$ to eat, weight becomes $3$; walk from $2$ back to $0$, spending $6$ units of energy. $1$ unit of energy remains.

Constraints

$0 \le x \le 10^6$.

$1 \le n \le 10^6$.

For each $1 \le i \le n$, $0 \le a_i \le x$.

Subtasks

1. (10 points) $n \le 12$
2. (20 points) $n \le 500$, $x \le 1000$
3. (30 points) $n \le 5000$
4. (40 points) No additional constraints.

Note

The sample grader reads input in the following format:

• First line: $n~x$
• Second line: $a[0]~a[1]~\cdots~a[n-1]$

The sample grader prints your output in the following format:

• One line, your return value