Du får $n$ tripplar av heltal $(a_i, b_i, c_i)$, sådana att $a_i < b_i < c_i$. Du måste välja ett par av värden från varje trippel och därmed bilda $n$ intervall. Du behöver välja paren så att varje par av skilda intervall har en snittlängd på noll. Hitta den maximalt möjliga summan av intervallens längder, eller ange att det är omöjligt att välja intervall som uppfyller villkoret.
Indata
Den första raden innehåller ett heltal $n$ — antalet tripplar. De följande $n$ raderna innehåller tre heltal $a_i$, $b_i$ och $c_i$ — den $i$:te trippeln.
Utdata
Om det är omöjligt att bilda intervall som uppfyller villkoret, skriv ut -1. Annars, skriv ut den maximalt möjliga summan av intervallens längder.
Begränsningar
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Exempel
Indata 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Utdata 1
7
Indata 2
3 1 2 4 1 2 4 1 2 4
Utdata 2
-1
Anmärkning
I det första exemplet finns det $n = 4$ tripplar: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ och $(4, 7, 8)$. En optimal lösning är: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Dessa intervall uppfyller villkoret att varje par av skilda intervall har snittlängd noll. Summan av deras längder är $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. I det andra exemplet är det omöjligt att välja intervallen så att villkoret uppfylls.