Intervals from Triplets
Обмеження: 3 сек., 512 МіБ
You are given \(n\) triplets of integers \((a_i, b_i, c_i)\), such that \(a_i < b_i < c_i\).
You have to choose a pair of values from each triplet and therefore form \(n\) intervals. You need to choose pairs such that every two distinct intervals have zero intersection length.
Find the maximum possible sum of lengths of intervals, or tell that it is impossible to choose intervals satisfying the condition.
Вхідні дані
The first line contains one integer \(n\) – the number of triplets.
The next \(n\) lines contain three integers \(a_i\), \(b_i\), and \(c_i\) – the \(i\)-th triplet.
Вихідні дані
If it is impossible to form intervals that satisfy the condition,
print -1. Otherwise, print the maximum possible sum of
lengths of intervals.
Обмеження
\(1 \le n \le 10^6\),
\(1 \le a_i < b_i < c_i \le 10^9\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 4 1 2 3 2 3 5 7 8 9 4 7 8 | 7 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 1 2 4 1 2 4 1 2 4 | -1 |
Примітки
In the first sample, there are \(n=4\) triplets: \((1, 2, 3)\), \((2, 3, 5)\), \((7, 8, 9)\), and \((4, 7, 8)\).
One optimal solution is: \((1, 2)\), \((2, 3)\), \((7, 9)\), \((4, 7)\). These intervals satisfy the condition that every two distinct intervals have zero intersection length. The sum of their lengths is \((2-1)+(3-2)+(9-7)+(7-4)=1+1+2+3=7\).
In the second sample, it is impossible to choose the intervals satisfying the condition.
Надіслати розв'язок
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|