Nobel, the famous programmer.Now he tries to arrange some programming class for his university juniors.He want to discuss some topics in the class.
So now,there are n topics that he want to discuss. For each topics, you know its starting and ending days and the amount of benefit you would get as reward.
His juniors can only attend one topic during a day
What is the maximum amount of benefit they can earn?
Between one topic no one can attend for another topics.If they are interested in another topics they must finish the running topics and start the next one but can not continue two topics at a time.
The first input line contains an integer n: the number of topics.
After this, there are n lines. Each such line has three integers Si, Ei, and Bi: the starting day, the ending day, and the amount of benefit of the ith topics.
1<=N<= 2* 10 ^5
1<=Si,Ei,Bi<=10^9
Print one integer: the maximum amount of benefit they can earn.
| Input | Output |
|---|---|
4 2 4 4 3 6 6 6 8 2 5 7 3 | 7 |
By attending the topics 1 and 4, his juniors get 4+3=7 which is the maximum amount of benefit. | |