Se te dan $n$ ternas de enteros $(a_i, b_i, c_i)$, tales que $a_i < b_i < c_i$. Debes elegir un par de valores de cada terna y formar así $n$ intervalos. Necesitas elegir los pares de modo que cada par de intervalos distintos tenga una intersección de longitud cero. Encuentra la suma máxima posible de las longitudes de los intervalos, o indica que es imposible elegir intervalos que cumplan la condición.
Entrada
La primera línea contiene un entero $n$ — el número de ternas. Las siguientes $n$ líneas contienen tres enteros $a_i$, $b_i$ y $c_i$ — la $i$-ésima terna.
Salida
Si es imposible formar intervalos que satisfagan la condición, imprime -1. En caso contrario, imprime la suma máxima posible de las longitudes de los intervalos.
Restricciones
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Ejemplos
Entrada 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Salida 1
7
Entrada 2
3 1 2 4 1 2 4 1 2 4
Salida 2
-1
Nota
En el primer ejemplo, hay $n = 4$ ternas: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ y $(4, 7, 8)$. Una solución óptima es: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Estos intervalos cumplen la condición de que cualesquiera dos intervalos distintos tienen longitud de intersección cero. La suma de sus longitudes es $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. En el segundo ejemplo, es imposible elegir los intervalos cumpliendo la condición.