F. Движение точек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На числовой прямой даны $$$n$$$ точек и $$$m$$$ отрезков. Изначальная координата $$$i$$$-й точки равна $$$a_i$$$. Левая и правая границы $$$j$$$-го отрезка это $$$l_j$$$ и $$$r_j$$$, соответственно.

Точки можно двигать. За одну операцию можно подвинуть любую точку из ее текущей координаты $$$x$$$ в координату $$$x - 1$$$ или в координату $$$x + 1$$$. Стоимость такого движения $$$1$$$.

Необходимо выполнить последовательность операций такую, чтобы каждый отрезок был посещён хотя бы одной точкой. Точка посетила отрезок $$$[l, r]$$$, если был такой момент, когда её координата принадлежала отрезку $$$[l, r]$$$ (включая границы).

Вы должны найти минимальную стоимость операций, которые нужно сделать, чтобы все отрезки были посещены.

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

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

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

Следующая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — изначальные координаты точек.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$l_j$$$ и $$$r_j$$$ ($$$-10^9 \le l_j \le r_j \le 10^9$$$) — левая и правая границы $$$j$$$-го отрезка соответственно.

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

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

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

Пример
Входные данные
2
4 11
2 6 14 18
0 3
4 5
11 15
3 5
10 13
16 16
1 4
8 12
17 19
7 13
14 19
4 12
-9 -16 12 3
-20 -18
-14 -13
-10 -7
-3 -1
0 4
6 11
7 9
8 10
13 15
14 18
16 17
18 19
Выходные данные
5
22
Примечание

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

  • Подвинуть вторую точку из координаты $$$6$$$ в координату $$$5$$$.
  • Подвинуть третью точку из координаты $$$14$$$ в координату $$$13$$$.
  • Подвинуть четвёртую точку из координаты $$$18$$$ в координату $$$17$$$.
  • Подвинуть третью точку из координаты $$$13$$$ в координату $$$12$$$.
  • Подвинуть четвёртую точку из координаты $$$17$$$ в координату $$$16$$$.

Суммарная стоимость всех действий равна $$$5$$$. Легко заметить, что все отрезки будут посещены после таких перемещений. Например, десятый отрезок ($$$[7, 13]$$$) будет посещён после второго перемещения третьей точкой.

Ниже рисунок, иллюстрирующий первый набор входных данных: