Statement : G0. Roadworks (all roads ready)

This is the easy version of G. Roadworks. Every road between consecutive houses already exists on day $1$; there is no road-building phase.

There are $n$ houses in a row, numbered $1$ to $n$. House $i$ has hospitality $h_i$. Adjacent houses are connected by a road.

You start at house $x$ on day $1$ with satisfaction $0$. For each day $s = 1, 2, \ldots, k$:

• You may move to an adjacent house or stay where you are;
• Your satisfaction increases by $h_j$, where $j$ is the house you are in after the move.

Find the maximum satisfaction after $k$ days.

Each test contains multiple test cases. The first line contains $t$ ($1 \le t \le 10^4$).

Each test case has:

• One line: $n$, $k$, $x$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$, $1 \le x \le n$);
• One line: $h_1, h_2, \ldots, h_n$ ($0 \le h_i \le 10^9$).

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, print one integer: the maximum satisfaction after $k$ days.

Input

4
5 10 3
14 2 3 5 6
4 8 1
0 0 0 1
2 1000000000 1
1 1000000000
2 5 1
10 1

Output

128
6
1000000000000000000
50

First test case ($n = 5$, $k = 10$, $x = 3$, $h = [14, 2, 3, 5, 6]$). All roads are available immediately. One optimal plan is to move to house $1$ early (hospitality $14$) and spend most remaining days there; the maximum is $128$.

Second test case ($n = 4$, $k = 8$, $x = 1$, only $h_4 = 1$ is positive). You need three moves to reach house $4$; the best schedule earns $1$ on days when you are at house $4$ and $0$ elsewhere. The maximum is $6$.

Third test case ($n = 2$, $k = 10^9$). Move to house $2$ on day $1$ and stay; you earn $10^9$ on each of $10^9$ days.

Fourth test case ($n = 2$, $k = 5$, $x = 1$, $h = [10, 1]$). Staying at house $1$ every day gives $5 \cdot 10 = 50$; moving to house $2$ is worse.

In the full problem, road $i$ between houses $i$ and $i + 1$ opens on day $d_i$. G0 is the special case $d_i = 1$ for every $i$: the graph is a path from day $1$ onward. The full solution keeps the same DP skeleton but computes different arrival times $T[i]$ from the array $d$. See editorial.md.