Du får gitt $n$ tripler av heltall $(a_i, b_i, c_i)$, slik at $a_i < b_i < c_i$. Du må velge et par av verdier fra hver trippel og dermed danne $n$ intervaller. Du må velge parene slik at enhver to forskjellige intervaller har snittlengde lik null. Finn den maksimalt mulige summen av lengdene til intervallene, eller oppgi at det er umulig å velge intervaller som oppfyller betingelsen.
Inndata
Den første linjen inneholder ett heltall $n$ — antallet tripler. De neste $n$ linjene inneholder tre heltall $a_i$, $b_i$ og $c_i$ — den $i$-te trippelen.
Utdata
Hvis det er umulig å danne intervaller som oppfyller betingelsen, skriv ut -1. Ellers, skriv ut den maksimalt mulige summen av lengdene til intervallene.
Begrensninger
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Eksempler
Inndata 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Utdata 1
7
Inndata 2
3 1 2 4 1 2 4 1 2 4
Utdata 2
-1
Merk
I det første eksempelet er det $n = 4$ tripler: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ og $(4, 7, 8)$. Én optimal løsning er: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Disse intervallene oppfyller betingelsen om at enhver to forskjellige intervaller har snittlengde null. Summen av lengdene deres er $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. I det andre eksempelet er det umulig å velge intervallene slik at betingelsen er oppfylt.