In an under-construction village, $n$ houses have been built in a row numbered from $1$ to $n$. House $i$ has hospitality $h_i$.

The village has $n - 1$ roads, where road $i$ connects houses $i$ and $i + 1$ and will be built on day $d_i$. Initially, no roads are built.

You start at house $x$ and will stay in the village from day $1$ to day $k$, initially with a satisfaction of $0$. On day $s$, the following happens in order:

• All roads $i$ with $d_i = s$ are built;
• You may move to an adjacent house, if the road to it has been built, or stay at your current house;
• Your satisfaction increases by $h_j$, where $j$ is the house you are currently at.

Find the maximum satisfaction you can achieve after $k$ days.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $k$ and $x$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$, $1 \le x \le n$) — the number of houses, the number of days and the starting house, respectively.

The second line contains $n$ integers $h_1, h_2, \ldots, h_n$ ($0 \le h_i \le 10^9$) — the hospitality of each house.

The third line contains $n - 1$ integers $d_1, d_2, \ldots, d_{n - 1}$ ($1 \le d_i \le k$) — the day each road is built.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the maximum satisfaction you can achieve after $k$ days.

Note

In the first test case, the following is one optimal sequence of moves:

• You start at house $x = 3$ with a satisfaction of $0$.
• On day $1$, no roads are built yet, so you must remain at house $3$. Your satisfaction becomes $3$.
• On day $2$, road $3$ is built. You move to house $4$ and remain there on days $2$, $3$, $4$, $5$, $6$ and $7$. Your satisfaction becomes $33$. During this time, roads $2$ and $4$ are also built.
• On day $8$, you move back to house $3$. Your satisfaction becomes $36$.
• On day $9$, you move to house $2$. Your satisfaction becomes $38$.
• On day $10$, road $1$ is built. You move to house $1$. Your satisfaction becomes $52$.

It can be shown that it is impossible to achieve a satisfaction greater than $52$.

In the second test case, you cannot reach house $4$ within $8$ days, so the maximum achievable satisfaction is $0$.

In the third test case, you can immediately move to house $2$ and remain there for $1\,000\,000\,000$ days.