魔理沙来魔法森林采蘑菇。
魔法森林可以用 $$$X$$$ 轴上编号为 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 点来表示。在玛丽莎开始之前,她的朋友帕秋莉用魔法检测了每个点上蘑菇的初始数量,用 $$$a_1,a_2,\ldots,a_n$$$ 表示。
玛丽莎可以在 $$$0$$$ 分钟内在森林中的任何地点出发。每分钟,以下事件按顺序发生:
- 她从$$$x$$$移动到$$$y$$$($$$|x-y|\le 1$$$,可能$$$y=x$$$)。
- 她收集了 $$$y$$$ 点上的所有蘑菇。
- 森林中的每个点都会出现一个新蘑菇。
请注意,她无法在 $$$0$$$ 分钟收集蘑菇。
现在,Marisa 想知道 $$$k$$$ 分钟后她可以采摘的蘑菇的最大数量。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,打印 Marisa 在 $$$k$$$ 分钟后可以采摘的蘑菇的最大数量。
示例
输入 #1
4 5 2 5 6 1 2 3 5 7 5 6 1 2 3 1 2 999999 5 70000 1000000000 1000000000 1000000000 1000000000 1000000000
输出 #1
12 37 1000000 5000349985
注意
测试用例1:
玛丽莎的起始价为$$$x=2$$$。在第一分钟,她移动到 $$$x=1$$$ 并收集 $$$5$$$ 蘑菇。蘑菇的数量将为$$$[1,7,2,3,4]$$$。在第二分钟,她移动到 $$$x=2$$$ 并收集 $$$7$$$ 蘑菇。蘑菇的数量将为$$$[2,1,3,4,5]$$$。 $$$2$$$ 分钟后,玛丽莎收集了 $$$12$$$ 蘑菇。
可以证明,不可能收集超过 $$$12$$$ 的蘑菇。
测试用例2:
这是她可能的移动路径之一:
$$$2 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$$$
可以证明,不可能收集超过 $$$37$$$ 的蘑菇。