Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shedule Matching

By subhashis_cse · 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.


    Discussion

    Statistics


    57% Solution Ratio

    CODER_RAFINEarliest, 2M ago

    RAKIBULHOSSAINFastest, 0.1s

    Nahid_039Lightest, 4.2 MB

    RUDRA_DASShortest, 736B

    Submit

    Login to submit