Danych jest $n$ trójek liczb całkowitych $(a_i, b_i, c_i)$, takich że $a_i < b_i < c_i$. Z każdej trójki musisz wybrać parę wartości, tworząc w ten sposób $n$ przedziałów. Pary należy wybrać tak, aby każde dwa różne przedziały miały przecięcie o długości zero. Znajdź maksymalną możliwą sumę długości przedziałów lub stwierdź, że nie da się wybrać przedziałów spełniających podany warunek.
Wejście
Pierwszy wiersz zawiera jedną liczbę całkowitą $n$ — liczbę trójek. Kolejne $n$ wierszy zawiera po trzy liczby całkowite $a_i$, $b_i$ oraz $c_i$ — $i$-tą trójkę.
Wyjście
Jeśli nie da się utworzyć przedziałów spełniających warunek, wypisz -1. W przeciwnym razie wypisz maksymalną możliwą sumę długości przedziałów.
Ograniczenia
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Przykłady
Wejście 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Wyjście 1
7
Wejście 2
3 1 2 4 1 2 4 1 2 4
Wyjście 2
-1
Uwaga
W pierwszym przykładzie mamy $n = 4$ trójki: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ oraz $(4, 7, 8)$. Jednym z optymalnych rozwiązań jest: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Przedziały te spełniają warunek, że każde dwa różne przedziały mają przecięcie o długości zero. Suma ich długości wynosi $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. W drugim przykładzie nie da się wybrać przedziałów spełniających warunek.