Черепаха только что получила \(n\) отрезков и последовательность \(a_1, a_2, \ldots, a_n\). \(i\)-й отрезок представляет собой \([l_i, r_i]\).
Черепаха создаст неориентированный граф \(G\). Если отрезок \(i\) и отрезок \(j\) пересекаются, то Черепаха добавит неориентированное ребро между \(i\) и \(j\) с весом \(|a_i - a_j|\), для каждого \(i \ne j\).
Черепаха хочет, чтобы вы вычислили сумму весов рёбер минимального остовного дерева графа \(G\), или сообщили, что у графа \(G\) нет остовного дерева.
Мы говорим, что два отрезка \([l_1, r_1]\) и \([l_2, r_2]\) пересекаются тогда и только тогда, когда \(\max(l_1, l_2) \le \min(r_1, r_2)\).
Выходные данные
Для каждого теста выведите одно целое число — сумму весов рёбер минимального остовного дерева графа \(G\). Если у графа \(G\) нет остовного дерева, выведите \(-1\).
Примечание
В первом тесте граф \(G\) выглядит следующим образом:
Одно из минимальных остовных деревьев \(G\) выглядит следующим образом:
Сумма весов рёбер минимального остовного дерева равна \(9\).
Во втором тесте граф \(G\) выглядит следующим образом:
\(G\) уже является деревом, и сумма весов дерева равна \(13\).
В третьем тесте граф \(G\) выглядит следующим образом:
В четвертом тесте граф \(G\) выглядит следующим образом:
Легко видеть, что \(G\) не связан, поэтому у \(G\) нет остовного дерева.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
1 7 3
2 4 6
3 5 5
6 7 9
3 4 4
5
2 7 3
1 3 6
4 5 5
6 7 9
1 1 4
4
1 4 3
1 2 1
3 4 5
1 4 4
3
1 3 1
2 3 3
4 5 8
|
9
13
4
-1
|