Problem Statement

Takahashi is at a ramen shop.

This shop has $N$ kinds of toppings, and the $i$-th topping has a price of $i$ and a happiness of $W_i$.

Takahashi chooses three distinct kinds of toppings so that the total price is at most $V$. Find the maximum possible total happiness of the toppings he chooses.

The constraints guarantee that there is at least one way to choose three distinct kinds of toppings so that the total price is at most $V$.

Constraints

• $3 \leq N \leq 100$
• $6 \leq V \leq 3N-3$
• $1 \leq W_i \leq 10^6$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

• $N$ $V$
• $W_1$ $W_2$ $\ldots$ $W_N$

Output

Output the answer in one line.

5 9
31 41 59 26 53

143

When choosing the first, third, and fifth toppings, the total price is $1+3+5=9$, and the total happiness is $31+59+53=143$.

10 16
102228 448944 131224 326172 500169 670309 976672 579051 974511 773940

2095925

When choosing the second, sixth, and seventh toppings, the total price is $2+6+7=15$, and the total happiness is $448944+670309+976672=2095925$.

• Source: AtCoder ABC 478 B