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

Это сложная версия задачи. Единственное различие состоит в том, что в этой версии $$$m \leq 10^9$$$.

Вам даны два массива целых чисел $$$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$$$, $$$1 \leq m \leq 10^9$$$) — размер массивов $$$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 4
1
3 2
4 7
5 1 5
3 8 3 3
8 4
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
Выходные данные
2
12
16
4
Примечание

В первом наборе входных данных:

  • Для пары массивов $$$([1, 1], [3, 2])$$$ ответ $$$0$$$. Можно не применять операции и не переставлять элементы.
  • Для пары массивов $$$([2, 1], [3, 2])$$$ ответ $$$0$$$. Можно переставить элементы первого массива, получить $$$[1, 2)$$$. Операции применять не нужно.
  • Для пары массивов $$$([3, 1], [3, 2])$$$ ответ $$$1$$$. Можно удалить $$$3$$$ из первого массива и $$$2$$$ из второго.
  • Для пары массивов $$$([4, 1], [3, 2])$$$ ответ $$$1$$$. Можно удалить $$$4$$$ из первого массива и $$$3$$$ из второго.