Dao and Dizzy's Date

The new year has come to Bubble Hill in Crazy Park. To celebrate, Dao and Dizzy are going on a date and plan to look around Bubble Hill.

Bubble Hill consists of $N$ places connected in a straight line. There are $N-1$ roads linking pairs of places: for each integer $i$ from $1$ to $N-1$, place $i$ and place $i+1$ are connected by a road.

Dao and Dizzy plan their date minute by minute. Each minute they choose one of the following three actions.

• If they are at place $i$ with $2 \leq i \leq N$, they take a road to place $i-1$.
• If they are at place $i$ with $1 \leq i \leq N-1$, they take a road to place $i+1$.
• They stay where they are.

Each minute, Dao and Dizzy gain happiness depending on the place $i$ they were at one minute earlier and the place $j$ they are at now. If $i \neq j$, they gain $h\_j$ happiness. The value $h\_j$ may be negative, which means they lose $-h\_j$ happiness. If $i = j$, their happiness does not change.

Only $T$ minutes remain for the date, so they want to start from the village, make their happiness as large as possible, and come back. That is, the starting and ending place must always be village 1, where Dao and Dizzy live. Find the happiness Dao and Dizzy will gain.

The first line gives two integers $N$ and $T$. ($2 \le N \le 100\,000$, $1 \le T \le 10^{9}$)

The second line gives $N$ integers separated by spaces; the $i$-th number is $h\_i$. ($-10^9 \le h\_i \le 10^9$, $h\_1 = 0$)

Print the maximum happiness Dao and Dizzy can gain on this date.