Universal Cup Judging System

Universal Cup

Limite de temps : 1.5 s Limite de mémoire : 512 MB Points totaux : 100
Statistiques

Вам даны $n$ троек целых чисел $(a_i, b_i, c_i)$, таких что $a_i < b_i < c_i$. Из каждой тройки необходимо выбрать пару значений и тем самым образовать $n$ отрезков. Пары нужно выбрать так, чтобы пересечение любых двух различных отрезков имело нулевую длину. Найдите максимально возможную сумму длин отрезков или определите, что выбрать отрезки, удовлетворяющие условию, невозможно.

Входные данные

Первая строка содержит одно целое число $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$. Во втором примере выбрать отрезки, удовлетворяющие условию, невозможно.

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.