Universal Cup Judging System

Universal Cup

حد الوقت: 1.5 s حد الذاكرة: 512 MB مجموع النقاط: 100
الإحصائيات

$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 番目の例では、条件を満たすように区間を選ぶことは不可能です。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.