Вам даны $n$ троек целых чисел $(a_i, b_i, c_i)$, таких что $a_i < b_i < c_i$. Из каждой тройки необходимо выбрать пару значений и тем самым образовать $n$ отрезков. Пары нужно выбрать так, чтобы пересечение любых двух различных отрезков имело нулевую длину. Найдите максимально возможную сумму длин отрезков или определите, что выбрать отрезки, удовлетворяющие условию, невозможно.
Входные данные
Первая строка содержит одно целое число $n$ — количество троек. Следующие $n$ строк содержат по три целых числа $a_i$, $b_i$ и $c_i$ — $i$-ю тройку.
Выходные данные
Если образовать отрезки, удовлетворяющие условию, невозможно, выведите -1. В противном случае выведите максимально возможную сумму длин отрезков.
Ограничения
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Примеры
Входные данные 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Выходные данные 1
7
Входные данные 2
3 1 2 4 1 2 4 1 2 4
Выходные данные 2
-1
Примечание
В первом примере даны $n = 4$ тройки: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ и $(4, 7, 8)$. Одно из оптимальных решений: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Эти отрезки удовлетворяют условию, что пересечение любых двух различных отрезков имеет нулевую длину. Сумма их длин равна $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. Во втором примере выбрать отрезки, удовлетворяющие условию, невозможно.