$a_i < b_i < c_i$ を満たす整数の三つ組 $(a_i, b_i, c_i)$ が $n$ 個与えられます。 各三つ組から 2 つの値を選び、それによって $n$ 個の区間を作らなければなりません。任意の 2 つの異なる区間の共通部分の長さが 0 になるようにペアを選ぶ必要があります。 区間の長さの総和としてあり得る最大値を求めるか、条件を満たすように区間を選ぶことが不可能であると判定してください。
入力
1 行目には 1 つの整数 $n$(三つ組の個数)が与えられます。 続く $n$ 行には、$i$ 番目の三つ組を表す 3 つの整数 $a_i$、$b_i$、$c_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
注記
1 番目の例では、$n = 4$ 個の三つ組 $(1, 2, 3)$、$(2, 3, 5)$、$(7, 8, 9)$、$(4, 7, 8)$ があります。 最適な選び方の 1 つは $(1, 2)$、$(2, 3)$、$(7, 9)$、$(4, 7)$ です。これらの区間は、任意の 2 つの異なる区間の共通部分の長さが 0 であるという条件を満たしています。長さの総和は $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$ です。 2 番目の例では、条件を満たすように区間を選ぶことは不可能です。