## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] The Enchanted Forest Codeforces Solution | Codeforces Problem Solution 2022

D. The Enchanted Forest
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Marisa comes to pick mushrooms in the Enchanted Forest.

The Enchanted forest can be represented by $n$ points on the $X$-axis numbered $1$ through $n$. Before Marisa started, her friend, Patchouli, used magic to detect the initial number of mushroom on each point, represented by ${a}_{1},{a}_{2},\dots ,{a}_{n}$.

Marisa can start out at any point in the forest on minute $0$. Each minute, the followings happen in order:

• She moves from point $x$ to $y$ ($|x-y|\le 1$, possibly $y=x$).
• She collects all mushrooms on point $y$.
• A new mushroom appears on each point in the forest.

Note that she cannot collect mushrooms on minute $0$.

Now, Marisa wants to know the maximum number of mushrooms she can pick after $k$ minutes.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1\le t\le {10}^{4}$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$$k$ ($1\le n\le 2\cdot {10}^{5}$$1\le k\le {10}^{9}$) — the number of positions with mushrooms and the time Marisa has, respectively.

The second line of each test case contains $n$ integers ${a}_{1},{a}_{2},\dots ,{a}_{n}$ ($1\le {a}_{i}\le {10}^{9}$) — the initial number of mushrooms on point $1,2,\dots ,n$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot {10}^{5}$.

Output

For each test case, print the maximum number of mushrooms Marisa can pick after $k$ minutes.