← 返回题目列表

Codeforces · 1687/A

A. 魔法森林

中文机器翻译题面 查看原题

魔理沙来魔法森林采蘑菇。

魔法森林可以用 $$$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$$$ 的蘑菇。