题目描述

有 $n$ 个房子排成一条线，第 $i$ 个房子的收益为 $h_i$。

相邻房子之间的道路会在指定日期建成。从某个房子 $x$ 出发并居住 $k$ 天；每天道路先建成，然后你可以移动到相邻且已连通的房子，或者留在原地。每天获得当前所在房子的收益。

求可以获得的最大总收益。

输入格式

每个测试包含多组测试数据。

第一行包含整数 $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$），表示第 $i$ 条道路建成的日期。

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

输出格式

对于每组测试数据，输出 $k$ 天后可以获得的最大满意度。

样例 1

4
5 10 3
14 2 3 5 6
10 6 2 7
4 8 1
0 0 0 1
7 1 2
2 1000000000 1
1 1000000000
1
9 27 6
17 13 5 8 14 3 4 17 20
10 1 2 13 3 15 6 23

52
0
1000000000000000000
386

约束与提示

• 时间限制：3 秒

• 内存限制：512 MB

• 原题编号：CF2229G