給定 $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$。 在第二個範例中,無法選擇滿足條件的區間。