CF2229G.Roadworks

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.

在一个正在建设中的村庄中，已有 $n$ 座房屋沿一条直线建成，编号从 $1$ 到 $n$。房屋 $i$ 的好客度为 $h_i$。

村庄中有 $n - 1$ 条道路，其中第 $i$ 条道路连接房屋 $i$ 和 $i + 1$，并在第 $d_i$ 天建成。初始时，没有任何道路建成。

你从房屋 $x$ 出发，并将在村庄中停留第 $1$ 天至第 $k$ 天，初始满意度为 $0$。在第 $s$ 天，将按以下顺序发生以下事件：

• 所有满足 $d_i = s$ 的道路 $i$ 均被建成；
• 你可以移动到一个相邻的房屋（前提是通往该房屋的道路已经建成），或者停留在当前房屋；
• 你的满意度增加 $h_j$，其中 $j$ 是你当前所在的房屋。

求经过 $k$ 天后你能达到的最大满意度。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$k$ 和 $x$（$2 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^9$，$1 \le x \le n$），分别表示房屋数量、天数和起始房屋编号。

第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$0 \le h_i \le 10^9$），表示每座房屋的亲和度。

第三行包含 $n - 1$ 个整数 $d_1, d_2, \ldots, d_{n - 1}$（$1 \le d_i \le k$），表示每条道路建成的日期。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

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

对于每个测试用例，输出一个整数——经过 $k$ 天后所能达到的最大满意度。

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.

在第一个测试用例中，以下是一种最优的移动序列：

• 你从房屋 $x = 3$ 出发，初始满意度为 $0$。
• 第 $1$ 天，尚无道路建成，因此你必须停留在房屋 $3$。你的满意度变为 $3$。
• 第 $2$ 天，道路 $3$ 建成。你移动至房屋 $4$，并在第 $2$、$3$、$4$、$5$、$6$ 和 $7$ 天均停留于该房屋。你的满意度变为 $33$。在此期间，道路 $2$ 和 $4$ 也相继建成。
• 第 $8$ 天，你返回房屋 $3$。你的满意度变为 $36$。
• 第 $9$ 天，你移动至房屋 $2$。你的满意度变为 $38$。
• 第 $10$ 天，道路 $1$ 建成。你移动至房屋 $1$。你的满意度变为 $52$。

可以证明，无法获得超过 $52$ 的满意度。

在第二个测试用例中，你无法在 $8$ 天内到达房屋 $4$，因此可达到的最大满意度为 $0$。

在第三个测试用例中，你可以立即移动至房屋 $2$ 并在那里停留 $1\,000\,000\,000$ 天。