C. Оптимальная вставка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть два массива $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_m$$$, состоящие из целых чисел.

Вы должны вставить все элементы массива $$$b$$$ в массив $$$a$$$ в произвольные места. В результате получится массив $$$c_1, c_2, \ldots, c_{n+m}$$$ размера $$$n + m$$$.

Обратите внимание, что элементы массива $$$a$$$ переставлять нельзя, но элементы массива $$$b$$$ можно вставлять куда угодно (в начало, между двумя соседними элементами массива $$$a$$$, в конец). Более того, элементы массива $$$b$$$ могут стоять в получившемся массиве в любом порядке.

Какое минимальное количество инверсий в массиве $$$c$$$ может быть? Напомним, что инверсией называется пара индексов $$$(i, j)$$$, такая что $$$i < j$$$ и $$$c_i > c_j$$$.

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

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

В первой строке каждого набора входных данных заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 10^6$$$).

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

Во третьей строке каждого набора заданы $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$).

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

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

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

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

Варианты оптимальных вставок для всех наборов входных данных (элементы массива $$$a$$$ подчеркнуты):

  • В первом наборе входных данных можно сделать $$$c = [\underline{1}, 1, \underline{2}, 2, \underline{3}, 3, 4]$$$.
  • Во втором наборе входных данных можно сделать $$$c = [1, 2, \underline{3}, \underline{2}, \underline{1}, 3]$$$.
  • В третьем наборе входных данных можно сделать $$$c = [\underline{1}, 1, 3, \underline{3}, \underline{5}, \underline{3}, \underline{1}, 4, 6]$$$.