Sinulle annetaan $n$ kokonaislukukolmikkoa $(a_i, b_i, c_i)$ siten, että $a_i < b_i < c_i$. Sinun täytyy valita jokaisesta kolmikosta lukupari ja muodostaa siten $n$ väliä. Parit on valittava niin, että jokaisen kahden eri välin leikkauksen pituus on nolla. Etsi suurin mahdollinen välien pituuksien summa tai ilmoita, että ehtoa toteuttavia välejä on mahdotonta valita.
Syöte
Ensimmäinen rivi sisältää yhden kokonaisluvun $n$ — kolmikoiden lukumäärän. Seuraavat $n$ riviä sisältävät kolme kokonaislukua $a_i$, $b_i$ ja $c_i$ — $i$:nnen kolmikon.
Tuloste
Jos ehtoa toteuttavia välejä on mahdotonta muodostaa, tulosta -1. Muussa tapauksessa tulosta suurin mahdollinen välien pituuksien summa.
Rajoitukset
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Esimerkit
Syöte 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Tuloste 1
7
Syöte 2
3 1 2 4 1 2 4 1 2 4
Tuloste 2
-1
Huomautus
Ensimmäisessä esimerkissä on $n = 4$ kolmikkoa: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ ja $(4, 7, 8)$. Yksi optimaalinen ratkaisu on: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Nämä välit täyttävät ehdon, että jokaisen kahden eri välin leikkauksen pituus on nolla. Niiden pituuksien summa on $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. Toisessa esimerkissä ehtoa toteuttavia välejä on mahdotonta valita.