G1. Танцы (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное различие состоит в том, что в этой версии $$$m = 1$$$.

Вам даны два массива целых чисел $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_n$$$. До начала применения операций вы можете переупорядочить элементы каждого из массивов как угодно. Дальше за одну операцию вы делаете оба следующих действия, если массивы не пусты:

  • Выбрать любой элемент из массива $$$a$$$ и удалить его (все остальные элементы в том же порядке сдвигаются в один новый массив $$$a$$$),
  • Выбрать любой элемент из массива $$$b$$$ и удалить его (все остальные элементы в том же порядке сдвигаются в один новый массив $$$b$$$).

Пусть $$$k$$$ — итоговый размер обоих массивов. Вам нужно найти наименьшее количество операций, чтобы выполнялось $$$a_i < b_i$$$ для всех $$$1 \leq i \leq k$$$.

Эта задача была слишком проста и автор задачи решил ее усложнить. Вам также дано натуральное число $$$m$$$. Теперь вам нужно найти сумму ответов на задачу для $$$m$$$ пар массивов $$$(c[i], b)$$$, где $$$1 \leq i \leq m$$$. Массив $$$c[i]$$$ получается из $$$a$$$ следующим образом:

  • $$$c[i]_1 = i$$$,
  • $$$c[i]_j = a_j$$$, для $$$2 \leq j \leq n$$$.
Входные данные

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

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

Вторая строка каждого набора входных данных содержит $$$n - 1$$$ целое число $$$a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$).

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

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

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

Пример
Входные данные
4
2 1
1
3 2
4 1
5 1 5
3 8 3 3
8 1
4 3 3 2 2 1 1
1 1 1 1 3 3 3 3
9 1
9 2 8 3 7 4 6 5
1 2 3 2 1 4 5 6 5
Выходные данные
0
1
4
4
Примечание

В первом наборе входных данных для пары массивов $$$([1, 1], [3, 2])$$$ ответ $$$0$$$. Можно не применять операции и не переставлять элементы.