Problem L
Live aid
Each musician has a certain potential for attention, and you want to maximize the total attention potential for the concert.
But the musicians are very stubborn. They require that they can choose when their performance starts and for how long it lasts. More specifically, all of them have given you a start time and end time for their performance. If you cannot guarantee this, they will not perform at all.
Input
The first line contains a single integer $1 \leq n \leq 150\, 000$, the number of musicians. Then follows $n$ lines, one for each musician. Each line contains three space-separated integers $s$, $e$ and $a$, where $0 \leq s \leq 10^6$ is the start time, $s < e \leq 10^6$ is the end time, and $0 \leq a \leq 10^6$ is the attention potential of the musician.
Output
Output the maximum total attention for the concert. In other words, pick a subset of the musicians to perform on the stage that maximize the sum of their attention potential, subject to the requirements that every musician gets their preferred time slot and there are no overlapping performances.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 0 2 3 5 10 6 1 7 10 8 10 2 |
12 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 0 1 1 1 2 1 |
2 |
