Hide

Problem L
Live aid

You are organizing the annual “Boost the Global Opulence” fundraiser concert and have received an extraordinarily amount of requests from musicians that want to perform. However, you only have one stage, so you can not invite all of them.

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

Please log in to submit a solution to this problem

Log in