Gefnar eru $n$ þrenndir heiltalna $(a_i, b_i, c_i)$, þannig að $a_i < b_i < c_i$. Þú þarft að velja par af gildum úr hverri þrennd og mynda þannig $n$ bil. Þú þarft að velja pörin þannig að hver tvö ólík bil hafi sniðmengi af lengd núll. Finndu hæstu mögulegu summu lengda bilanna, eða segðu til um að ómögulegt sé að velja bil sem uppfylla skilyrðið.
Inntak
Fyrsta línan inniheldur eina heiltölu $n$ — fjölda þrennda. Næstu $n$ línur innihalda þrjár heiltölur $a_i$, $b_i$ og $c_i$ — $i$-tu þrenndina.
Úttak
Ef ómögulegt er að mynda bil sem uppfylla skilyrðið skal prenta -1. Annars skal prenta hæstu mögulegu summu lengda bilanna.
Takmarkanir
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$.
Dæmi
Inntak 1
4 1 2 3 2 3 5 7 8 9 4 7 8
Úttak 1
7
Inntak 2
3 1 2 4 1 2 4 1 2 4
Úttak 2
-1
Athugasemd
Í fyrra dæminu eru $n = 4$ þrenndir: $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$ og $(4, 7, 8)$. Ein besta lausnin er: $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$. Þessi bil uppfylla það skilyrði að hver tvö ólík bil hafa sniðmengi af lengd núll. Summa lengda þeirra er $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$. Í seinna dæminu er ómögulegt að velja bilin þannig að skilyrðið sé uppfyllt.