F. AND x OR
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Suppose you have two arrays $$$c$$$ and $$$d$$$, each of length $$$k$$$. The pair $$$(c, d)$$$ is called good if $$$c$$$ can be changed to $$$d$$$ by performing the following operation any number of times.

  • Select two distinct indices $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq k$$$, $$$i \neq j$$$) and a nonnegative integer $$$x$$$ ($$$0 \leq x < 2^{30}$$$). Then, apply the following transformations:

You are given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$, containing nonnegative integers not exceeding $$$m$$$.

You can perform two types of moves on these arrays any number of times:

  1. Select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and set $$$a_i := a_i + 1$$$.
  2. Select an index $$$i$$$ ($$$1 \leq i \leq n$$$) and set $$$b_i := b_i + 1$$$.

Note that the elements of $$$a$$$ and $$$b$$$ may exceed $$$m$$$ at some point while performing the moves.

Find the minimum number of moves required to make the pair $$$(a, b)$$$ good.

Input

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 two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^6$$$) — the length of arrays $$$a$$$ and $$$b$$$, and the maximum possible value in these arrays, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq m$$$) — denoting the array $$$a$$$.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i \leq m$$$) — denoting the array $$$b$$$.

Additionally, it is guaranteed that the sum of all values of $$$n$$$ and the sum of all values of $$$m$$$ across all test cases do not exceed $$$2 \cdot 10^6$$$.

Output

For each test case, output a single integer — the minimum number of moves required to make the pair $$$(a, b)$$$ good.

Example
Input
5
4 3
0 1 2 3
0 1 2 3
3 32
8 9 32
8 6 32
5 64
5 7 16 32 64
4 8 16 32 64
4 11
9 1 4 3
8 11 6 2
5 10
7 9 5 4 2
3 10 6 5 9
Output
0
2
2
0
1
Note

In the first case, we already have $$$a = b$$$.

In the second case, we can perform move $$$2$$$ on index $$$i = 2$$$ twice. The array $$$b$$$ becomes $$$[8, 8, 32]$$$. We can see that $$$(a, b)$$$ is now good.

In the third case, we can perform move $$$2$$$ on index $$$i = 1$$$, then perform move $$$1$$$ on index $$$i = 2$$$. It can be proven that you cannot make the pair $$$(a, b)$$$ good in fewer than $$$2$$$ moves.