На числовой прямой даны \(n\) точек и \(m\) отрезков. Изначальная координата \(i\)-й точки равна \(a_i\). Левая и правая границы \(j\)-го отрезка это \(l_j\) и \(r_j\), соответственно.
Точки можно двигать. За одну операцию можно подвинуть любую точку из ее текущей координаты \(x\) в координату \(x - 1\) или в координату \(x + 1\). Стоимость такого движения \(1\).
Необходимо выполнить последовательность операций такую, чтобы каждый отрезок был посещён хотя бы одной точкой. Точка посетила отрезок \([l, r]\), если был такой момент, когда её координата принадлежала отрезку \([l, r]\) (включая границы).
Вы должны найти минимальную стоимость операций, которые нужно сделать, чтобы все отрезки были посещены.
Выходные данные
Для каждого набора входных данных выведите одно число — минимальную суммарную стоимость всех перемещений, чтобы посетить все отрезки.
Примечание
В первом наборе входных данных точки можно двигать следующим образом:
- Подвинуть вторую точку из координаты \(6\) в координату \(5\).
- Подвинуть третью точку из координаты \(14\) в координату \(13\).
- Подвинуть четвёртую точку из координаты \(18\) в координату \(17\).
- Подвинуть третью точку из координаты \(13\) в координату \(12\).
- Подвинуть четвёртую точку из координаты \(17\) в координату \(16\).
Суммарная стоимость всех действий равна \(5\). Легко заметить, что все отрезки будут посещены после таких перемещений. Например, десятый отрезок (\([7, 13]\)) будет посещён после второго перемещения третьей точкой.
Ниже рисунок, иллюстрирующий первый набор входных данных:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|