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$개 주어집니다. 각 삼중쌍에서 두 개의 값을 선택하여 총 $n$개의 구간을 만들어야 합니다. 이때 서로 다른 임의의 두 구간의 교집합의 길이가 0이 되도록 쌍을 선택해야 합니다. 구간들의 길이의 합의 최댓값을 구하거나, 조건을 만족하도록 구간을 선택하는 것이 불가능함을 판별하시오.

입력

첫 번째 줄에 삼중쌍의 개수를 나타내는 정수 $n$이 주어집니다. 다음 $n$개의 줄에는 $i$번째 삼중쌍을 나타내는 세 정수 $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

노트

첫 번째 예제에서는 $n = 4$개의 삼중쌍 $(1, 2, 3)$, $(2, 3, 5)$, $(7, 8, 9)$, $(4, 7, 8)$이 있습니다. 최적의 해 중 하나는 $(1, 2)$, $(2, 3)$, $(7, 9)$, $(4, 7)$입니다. 이 구간들은 서로 다른 임의의 두 구간의 교집합의 길이가 0이라는 조건을 만족합니다. 구간 길이의 합은 $(2 - 1) + (3 - 2) + (9 - 7) + (7 - 4) = 1 + 1 + 2 + 3 = 7$입니다. 두 번째 예제에서는 조건을 만족하도록 구간을 선택하는 것이 불가능합니다.

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.