题目描述

有 \(n\) 个储蓄罐，从左到右编号为 \(1\) 到 \(n\)。初始时，第 \(i\) 个储蓄罐中有 \(a_i\) 单位雨水。

你有两辆雨水收集车。在第 \(0\) 天（还未开始下雨前），你可以将两辆车放在任意两个储蓄罐前（可以在同一个位置）。

接下来连续进行 \(k\) 天。每一天按以下顺序发生：

• 每个储蓄罐都会增加 \(1\) 单位雨水；
• 两辆收集车分别收集自己当前位置储蓄罐中的全部雨水；
• 若两辆车在同一个储蓄罐前，则该储蓄罐的雨水只会被收集一次；
• 每辆车可以选择：不移动，或移动到相邻位置（从 \(i\) 到 \(i-1\) 或 \(i+1\)），且不能移出区间 \([1, n]\)。

请你计算：经过 \(k\) 天后，两辆收集车最多可以收集多少单位雨水。

数据范围： \(1 \le n \le 2 \times 10^5\)， \(1 \le k \le 10^9\)， \(0 \le a_i \le 10^9\)。

输入格式

第一行一个整数 \(T\)，表示测试数据组数。对于本题要求， \(T = 5\)。

接下来每组数据包含两行：

• 第一行两个整数 \(n, k\)；
• 第二行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)。

输出格式

对每组数据，输出一行一个整数，表示最多能收集到的雨水总量。

样例输入

5
1 3
2
2 1
1 2
3 2
0 0 0
4 2
1 0 2 0
5 3
3 1 4 1 5

样例输出

5
5
5
9
25