Ti vengono date $n$ terne di interi $(a_i, b_i, c_i)$, tali che $a_i < b_i < c_i$. Devi scegliere una coppia di valori da ciascuna terna e formare quindi $n$ intervalli. Devi scegliere le coppie in modo tale che ogni due intervalli distinti abbiano intersezione di lunghezza zero. Trova la massima somma possibile delle lunghezze degli intervalli, oppure indica che è impossibile scegliere intervalli che soddisfino la condizione.
Input
La prima riga contiene un intero $n$ — il numero di terne. Le successive $n$ righe contengono tre interi $a_i$, $b_i$ e $c_i$ — la $i$-esima terna.
Output
Se è impossibile formare intervalli che soddisfino la condizione, stampa -1. Altrimenti, stampa la massima somma possibile delle lunghezze degli intervalli.
Vincoli
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Esempi
Input 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Output 1
7
Input 2
3 1 2 4 1 2 4 1 2 4
Output 2
-1
Note
Nel primo esempio, ci sono $n = 4$ terne: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ e $(4, 7, 8)$. Una soluzione ottima è: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Questi intervalli soddisfano la condizione secondo cui ogni due intervalli distinti hanno intersezione di lunghezza zero. La somma delle loro lunghezze è $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. Nel secondo esempio, è impossibile scegliere gli intervalli soddisfacendo la condizione.