Shedule Matching

subhashis_cse STP Coding Test 25 Jan 20...
Limits 1s, 512 MB

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.

Input

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

Output

Print one integer: the maximum amount of benefit they can earn.

Sample

InputOutput
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.


Submit

Login to submit.

Statistics

65% Solution Ratio
CODER_RAFINEarliest, Jan '21
steinumFastest, 0.0s
steinumLightest, 5.5 kB
steinumShortest, 716B
Toph uses cookies. By continuing you agree to our Cookie Policy.