F. Square Permutation I
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Give two permutations $$$p$$$ and $$$q$$$ of length $$$n$$$. It is guaranteed that $$$n$$$ is an odd number. You must perform exactly one of the following operations for each position $$$i \in [1,n]$$$:

  1. Perform no operation at no cost.
  2. Spend a cost of $$$x_i$$$ to either modify $$$p_i$$$ to $$$p_i^2$$$ or modify $$$q_i$$$ to $$$q_i^2$$$.
  3. Spend a cost of $$$y_i$$$ to modify both $$$p_i$$$ to $$$p_i^2$$$ and $$$q_i$$$ to $$$q_i^2$$$.

Please find the minimum cost required to make the median of array $$$p$$$ equal to $$$A$$$ and the median of array $$$q$$$ equal to $$$B$$$. If it's impossible, output $$$-1$$$.

Input

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

The first line of each test case contains three single integers $$$n,A,B$$$ $$$(1 \leq n \leq 10^5,1 \leq A,B \leq n^2)$$$.

The second line gives $$$n$$$ positive integers, representing the permutation $$$p$$$.

The third line gives $$$n$$$ positive integers, representing the permutation $$$q$$$.

The fourth line gives $$$n$$$ positive integers, representing the array $$$x$$$ .

The fifth line gives $$$n$$$ positive integers, representing the array $$$y$$$ $$$(1 \leq x_i \leq y_i \leq10^4)$$$.

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

Output

For each test case, output $$$-1$$$ if it is impossible.

Otherwise, output the minimum cost.

All outputs must be printed on separate lines.

Example
Input
3
7 6 7
7 3 5 6 2 4 1
1 6 3 4 2 7 5
5 1 1 4 4 1 1
6 4 6 6 6 1 1
9 5 5
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9 9
3 2 3
1 2 3
2 3 1
10000 1 1
10000 1 1
Output
7
0
10000