У Parsa есть огромное дерево на \(n\) вершинах.
На каждой вершине \(v\) он записал два целых числа \(l_v\) и \(r_v\).
Чтобы дерево Parsa выглядело еще более величественным, Nima хочет назначить число \(a_v\) (\(l_v \le a_v \le r_v\)) для каждой вершины \(v\) таким образом, чтобы красота дерева Parsa была максимальной.
Восприятие красоты Nima довольно причудливо. Он определяет красоту дерева как сумму \(|a_u - a_v|\) по всем ребрам \((u, v)\) дерева.
Поскольку дерево Parsa слишком велико, Nima не может самостоятельно максимизировать его красоту. Ваша задача — найти максимальную возможную красоту для дерева Parsa.
Выходные данные
Для каждого набора входных данных выведите максимальную возможную красоту для дерева Парса.
Примечание
Деревья в примере:
В первом наборе входных данных одно из возможных назначений — \(a = \{1, 8\}\), что приводит к \(|1 - 8| = 7\).
Во втором наборе входных данных одно из возможных назначений — \(a = \{1, 5, 9\}\), что приводит к красоте \(|1 - 5| + |5 - 9| = 8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6
|
7
8
62
|