F. И x ИЛИ
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Предположим, у вас есть два массива $$$c$$$ и $$$d$$$, каждый длиной $$$k$$$. Пара $$$(c, d)$$$ называется хорошей, если $$$c$$$ можно преобразовать в $$$d$$$, выполнив следующую операцию некоторое количество раз.

  • Выберите два различных индекса $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \leq k$$$, $$$i \neq j$$$) и неотрицательное целое число $$$x$$$ ($$$0 \leq x \lt 2^{30}$$$). Затем примените следующие преобразования:

Вам даны два массива $$$a$$$ и $$$b$$$, оба длиной $$$n$$$, содержащие неотрицательные целые числа, не превышающие $$$m$$$.

Вы можете любое число раз выполнять два типа ходов, которые изменяют эти массивы:

  1. Выберите индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и присвойте $$$a_i := a_i + 1$$$.
  2. Выберите индекс $$$i$$$ ($$$1 \leq i \leq n$$$) и присвойте $$$b_i := b_i + 1$$$.

Обратите внимание, что элементы $$$a$$$ и $$$b$$$ могут превышать $$$m$$$ в какой-то момент во время выполнения операций.

Найдите минимальное количество ходов, необходимых для того, чтобы сделать пару $$$(a, b)$$$ хорошей.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^6$$$) — длина массивов $$$a$$$ и $$$b$$$, и максимальное возможное значение в этих массивах соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq m$$$) — массив $$$a$$$.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i \leq m$$$) — массив $$$b$$$.

Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходят $$$2 \cdot 10^6$$$.

Выходные данные

Для каждого набора выведите одно целое число — минимальное количество ходов, необходимое для того, чтобы сделать пару $$$(a, b)$$$ хорошей.

Пример
Входные данные
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
Выходные данные
0
2
2
0
1
Примечание

В первом наборе входных данных изначально $$$a = b$$$.

Во втором наборе мы можем выполнить ход $$$2$$$ типа на индексе $$$i = 2$$$ дважды. Массив $$$b$$$ становится равен $$$[8, 8, 32]$$$. Можно показать, что пара $$$(a, b)$$$ стала хорошей.

В третьем наборе мы можем выполнить ход $$$2$$$ типа на индексе $$$i = 1$$$, затем выполнить ход $$$1$$$ типа на индексе $$$i = 2$$$. Можно доказать, что невозможно сделать пару $$$(a, b)$$$ хорошей менее чем за $$$2$$$ хода.