题目描述

Starlight Glimmer 正在指挥小马们割神奇的韭菜，每匹小马都被分配到韭菜地的某一行。

对于某匹小马来说，在时间 $0$ 时，这行韭菜的高度是 $v_1,v_2,\dots,v_n$，小马的位置是 $p$。

在时间 $t$（$t\ge 1$）开始时，由于魔法的作用，每棵韭菜都长高了 $k$ 个单位，然后小马立即割掉了它所在位置的韭菜，最后小马可以选择是否移动到相邻的位置。

现在有些小马想知道在 $t_0$ 时间内可以割多少单位的韭菜。

对于每组数据，形式如下：

在时间 $0$ 时，有一个初始数组 $v_1,v_2,\dots,v_n$，其指针指向 $p$ 位置和 $sum$ 的 $0$。

在时间 $t$（$t\ge 1$）开始时，依次执行以下操作：

1. 对每个 $i$ 执行 $v_i\leftarrow v_i + k$。
2. $sum\leftarrow sum + v_p$。
3. $v_p\leftarrow 0$。
4. $p\leftarrow p'\in \{p,\max(p-1,1),\min(p+1,n)\}$。

求 $sum$ 在时间 $t_0$ 结束时的最大值。

输入格式

有多个测试用例。第一行包含一个整数 $T$ ( $1\le T\le 10^5$ ) 表示每个测试用例的测试用例数：

第一行包含两个整数 $n,p$ ( $1\le n\le 2\times 10^5, 1\le p \le n$ ) 表示数组长度和指针位置。

第二行包含 $n$ 个整数 $v_1, v_2, \ldots, v_n$ （ $0\le v_i\le 10^6$ ）表示初始数组。

第三行包含两个整数 $k, t_0$ ( $0 \le k \le 10^6, 1\le t_0\le 10^6$ ) 表示增长参数和查询时间。

保证所有数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，在一行中打印一个整数，代表最大值 $sum$。

3
6 3
1 1 4 5 1 4
3 2
6 3
1 1 4 5 1 4
3 3
6 3
1 1 4 5 1 4
3 4

18
28
44