畀定 $n$ 個整數三元組 $(a_i, b_i, c_i)$,滿足 $a_i < b_i < c_i$。 你需要從每個三元組入面揀一對數值,從而構成 $n$ 個區間。你需要揀出呢啲區間,使得任意兩個唔同區間嘅交集長度為零。 求區間長度總和嘅最大值,如果無法揀出滿足條件嘅區間,就輸出 -1。
輸入格式
第一行包含一個整數 $n$ —— 三元組嘅數量。 接落嚟嘅 $n$ 行,每行包含三個整數 $a_i$、$b_i$ 同 $c_i$ —— 第 $i$ 個三元組。
輸出格式
如果無法構成滿足條件嘅區間,輸出 -1。否則,輸出區間長度總和嘅最大值。
數據範圍
$1 \le n \le 10^6$, $1 \le a_i < b_i < c_i \le 10^9$。
範例
輸入 1
4 1 2 3 2 3 5 7 8 9 4 7 8
輸出 1
7
輸入 2
3 1 2 4 1 2 4 1 2 4
輸出 2
-1
說明
喺第一個範例入面,有 $n = 4$ 個三元組:$(1, 2, 3)$、$(2, 3, 5)$、$(7, 8, 9)$ 同 $(4, 7, 8)$。 一個最優解係:$(1, 2)$、$(2, 3)$、$(7, 9)$、$(4, 7)$。呢啲區間滿足任意兩個唔同區間嘅交集長度為零嘅條件。佢哋嘅長度總和為 $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$。 喺第二個範例入面,無法揀出滿足條件嘅區間。