Intervals from Triplets
Limits: 3 sec., 512 MiB
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.
Input
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.
Output
If it is impossible to form intervals that satisfy the condition,
print -1. Otherwise, print the maximum possible sum of
lengths of intervals.
Constraints
\(1 \le n \le 10^6\),
\(1 \le a_i < b_i < c_i \le 10^9\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 2 3 2 3 5 7 8 9 4 7 8 | 7 |
| Input (stdin) | Output (stdout) |
|---|---|
| 3 1 2 4 1 2 4 1 2 4 | -1 |
Notes
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.
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|