G. Taffy vs Goblins
time limit per test
1 second
memory limit per test
1024 МБ
input
standard input
output
standard output

Mage Taffy is fighting against $$$N$$$ goblins. She will cast $$$N$$$ magic missiles, where the $$$i$$$-th missile is fixed to attack the $$$i$$$-th goblin.

It is known that the $$$i$$$-th missile has penetration power $$$A_i$$$ and potential damage $$$C_i$$$, while the $$$i$$$-th goblin has defense $$$B_i$$$. The missile deals $$$C_i$$$ damage if and only if its penetration power is at least the goblin's defense, that is, $$$A_i \ge B_i$$$; otherwise, it deals $$$0$$$ damage.

Taffy has one chance to use a secret spell: before damage is resolved, she may choose at most one missile and forcibly change its penetration power to $$$X$$$ (or she may choose not to modify any missile).

Now there are $$$Q$$$ independent queries. Each query gives a value $$$X$$$. For the current given $$$X$$$, please determine the maximum total damage Taffy can deal to the goblins under the optimal modification strategy.

Input

The input contains multiple test cases.

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$), denoting the number of test cases.

For each test case:

The first line contains two integers $$$N, Q$$$ ($$$1 \le N, Q \le 2 \cdot 10^5$$$), denoting the number of goblins (and missiles) and the number of queries, respectively.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$.

The third line contains $$$N$$$ integers $$$B_1, B_2, \dots, B_N$$$.

The fourth line contains $$$N$$$ integers $$$C_1, C_2, \dots, C_N$$$.

The next $$$Q$$$ lines each contain one integer $$$X$$$, representing the given modification value for a query.

Constraints:

  • $$$1 \le A_i, B_i, C_i, X \le 10^9$$$
  • It is guaranteed that for each test file, the sum of all $$$N$$$ and the sum of all $$$Q$$$ over all test cases do not exceed $$$2 \cdot 10^5$$$, respectively.
Output

For each test case, output $$$Q$$$ lines. Each line should contain one integer, representing the maximum total damage Taffy can deal to the goblins for the corresponding modification value $$$X$$$.

Example
Input
1
5 4
1 2 4 5 6
3 1 5 8 7
1 5 5 2 1
3
1
7
8
Output
6
5
10
10
Note

Initially, without using the secret spell, only the $$$2$$$nd missile hits, so the base damage is $$$5$$$.

For the first query $$$X = 3$$$: modify the $$$1$$$st missile. Since $$$3 \ge B_1$$$, it deals an additional $$$1$$$ point of damage. The maximum total damage is $$$5 + 1 = 6$$$.

For the second query $$$X = 1$$$: modifying any missile that originally misses still cannot make it satisfy the hit condition, so not modifying any missile is optimal. The maximum total damage remains the base value $$$5$$$.

For the third query $$$X = 7$$$: modifying the $$$3$$$rd missile is optimal. Since $$$7 \ge B_3$$$, it deals an additional $$$5$$$ points of damage. The maximum total damage is $$$5 + 5 = 10$$$.

For the fourth query $$$X = 8$$$: it is still optimal to modify the $$$3$$$rd missile (for a total damage of $$$10$$$); if the $$$4$$$th missile were modified instead, the total damage would only be $$$5 + 2 = 7$$$. Therefore, the maximum total damage is still $$$10$$$.