D. Changes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two lists $$$X = (x_1, \ldots, x_n)$$$ and $$$Y = (y_1, \ldots, y_n)$$$ of $$$n$$$ integers, we say that $$$X$$$ is dominated by $$$Y$$$ if $$$x_i \leq y_i$$$ for all $$$i = 1, 2, \ldots, n$$$. We say that $$$X$$$ is dominated by a reordering of $$$Y$$$ if $$$Y$$$ can be rearranged in such a way that $$$X$$$ is dominated by $$$Y$$$: formally, if there exists a permutation $$$\sigma$$$ such that $$$x_i \leq y_{\sigma(i)}$$$ for all $$$i = 1, 2, \ldots, n$$$.

Three lists $$$A$$$, $$$B$$$, $$$C$$$ of $$$n$$$ integers are given. The following operation can be performed: exchange the element $$$a_i$$$ with the element $$$b_i$$$, for $$$1 \leq i \leq n$$$.

Find the minimum number of operations necessary so that, after performing the operations, $$$A$$$ is dominated by a reordering of $$$C$$$. If this is not possible, print $$$-1$$$.

Input

The first line contains an integer $$$T$$$, the number of cases to process.

Each case begins with a line containing $$$n$$$, the size of the lists $$$A$$$, $$$B$$$, and $$$C$$$.

The next line of each case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

The next line of each case contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$.

The next line of each case contains $$$n$$$ integers $$$c_1, \ldots, c_n$$$.

Output

For each case, print an integer, the minimum number of operations or $$$-1$$$ if it is not possible to make $$$A$$$ dominated by a reordering of $$$C$$$.

Scoring
  1. (22 points) $$$a_i, b_i, c_i \le 2$$$ for all $$$1 \leq i \leq n$$$.
  2. (23 points) $$$b_i = a_i - 1$$$ for all $$$1 \leq i \leq n$$$.
  3. (24 points) The sum of $$$n$$$ over all cases will be less than or equal to $$$10^3$$$.
  4. (31 points) Without additional restrictions.
Example
Input
3
3
1 2 3
3 3 3
1 2 2
3
1 3 2
1 1 1
2 1 1
2
2 3
4 3
4 2
Output
-1
1
0
Note

$$$1 \le T \le 10^5$$$.

$$$1 \le n \le 10^5$$$.

The sum of $$$n$$$ over all cases will be less than or equal to $$$10^5$$$.

$$$1 \le a_i, b_i, c_i \le 10^9$$$.