CF1687A.The Enchanted Forest

The enchanted forest got its name from the magical mushrooms growing here. They may cause illusions and generally should not be approached.

—Perfect Memento in Strict Sense

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,\ldots,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.

被施了魔法的森林因其生长于此的魔法蘑菇而得名。这些蘑菇可能引发幻觉，通常不应靠近。

——《严正意义上的完美记忆》

玛莉萨来到被施了魔法的森林中采摘蘑菇。

被施了魔法的森林可表示为 $X$ 轴上的 $n$ 个点，编号为 $1$ 至 $n$。在玛莉萨出发前，她的朋友帕秋莉已用魔法探测出每个点上初始的蘑菇数量，记为 $a_1, a_2, \ldots, a_n$。

玛莉萨可在第 $0$ 分钟时从森林中任意一点出发。此后，每分钟内将按顺序发生以下事件：

• 她从点 $x$ 移动到点 $y$（满足 $|x - y| \le 1$，即允许停留在原地 $y = x$）；
• 她采集点 $y$ 上的所有蘑菇；
• 森林中每个点上均长出一枚新蘑菇。

注意：她在第 $0$ 分钟不能采集蘑菇。

现在，玛莉萨想知道：经过 $k$ 分钟后，她最多能采集多少枚蘑菇？

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 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,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the initial number of mushrooms on point $1,2,\ldots,n$.

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10 ^ 5$，$1\le k \le 10^9$），分别表示长有蘑菇的位置数量以及 Marisa 拥有的时间。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$），表示位置 $1,2,\ldots,n$ 上初始的蘑菇数量。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10 ^ 5$。

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

对于每个测试用例，输出 Marisa 在 $k$ 分钟后能够采摘的蘑菇的最大数量。

Test case 1:

Marisa can start at $x=2$. In the first minute, she moves to $x=1$ and collect $5$ mushrooms. The number of mushrooms will be $[1,7,2,3,4]$. In the second minute, she moves to $x=2$ and collects $7$ mushrooms. The numbers of mushrooms will be $[2,1,3,4,5]$. After $2$ minutes, Marisa collects $12$ mushrooms.

It can be shown that it is impossible to collect more than $12$ mushrooms.

Test case 2:

This is one of her possible moving path:

$2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$

It can be shown that it is impossible to collect more than $37$ mushrooms.

测试用例 1：

Marisa 可以从 $x=2$ 出发。第一分钟，她移动到 $x=1$ 并采集 $5$ 个蘑菇。此时蘑菇数量变为 $[1,7,2,3,4]$。第二分钟，她移动到 $x=2$ 并采集 $7$ 个蘑菇。此时蘑菇数量变为 $[2,1,3,4,5]$。经过 $2$ 分钟后，Marisa 共采集了 $12$ 个蘑菇。

可以证明，无法采集超过 $12$ 个蘑菇。

测试用例 2：

这是她的一条可能的移动路径：

$2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$

可以证明，无法采集超过 $37$ 个蘑菇。