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.

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

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

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.