B. Magic Leeks
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Starlight Glimmer is directing the ponies to cut magical leeks, and each pony is assigned a particular row in the leek field.

For a given pony, the height of this row of leeks at time $$$0$$$ is $$$v_1,v_2,\dots,v_n$$$, and the pony is at position $$$p$$$.

At the beginning of time $$$t$$$ ($$$t\ge 1$$$), each leek grows $$$k$$$ units taller due to magic, then the pony instantly cuts the leek in its position, and finally the pony has the option to move to an adjacent position or not.

Now some ponies want to know how many units of leeks they can cut in the time $$$t_0$$$.

Formally, for each set of data:

At time $$$0$$$, there is an initial array $$$v_1,v_2,\dots,v_n$$$ with a pointer to the $$$p$$$ position and $$$sum$$$ of $$$0$$$.

At the beginning of time $$$t$$$ ($$$t\ge 1$$$), the following operations are performed in sequence:

  1. performs $$$v_i\leftarrow v_i + k$$$ for each $$$i$$$.
  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)\}$$$.

Find the maximum value of $$$sum$$$ at the end of time $$$t_0$$$.

Input

There are multiple test cases. The first line contains an integer $$$T$$$ ($$$1\le T\le 10^5$$$) indicating the number of test cases, for each test case:

The first line contain two integers $$$n,p$$$ ($$$1\le n\le 2\times 10^5, 1\le p \le n$$$) indicating the length of the array and the pointer position.

The second line contain $$$n$$$ integers $$$v_1, v_2, \ldots, v_n$$$ ($$$0\le v_i\le 10^6$$$), represents the initial array.

The third line contains two integers $$$k, t_0$$$ ($$$0 \le k \le 10^6, 1\le t_0\le 10^6$$$) indicating the growth parameter and the interrogation time.

It is guaranteed that the sum of $$$n$$$ in all data does not exceed $$$10^6$$$.

Output

For each test case, print a single integer on a line, represents maximum value of $$$sum$$$.

Example
Input
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
Output
18
28
44