Contest

Interview

Time limit1sMemory limit256 MB

Summary
Given N intervals with start time, end time, and prize money, choose non-overlapping contests (end must not touch the next start) to maximize total prize.
Level

Medium5 of 10

Topics
Dynamic programming, Sorting, Binary search, Intervals
Solved
No attempts yet

Statement

Seungmin is the best programmer in the world, and everyone knows that he takes first place whenever he enters a contest. He has decided to enter several programming contests to earn prize money, and there are NN contests in total.

Naturally, if contests overlap in time, he cannot enter several of them at once. So, given the start time, end time, and prize money of each of the NN contests, Seungmin will enter contests in a way that earns him the most prize money. Naturally, he can receive the prize money from every contest he enters. Also, to allow for travel time, the end time of a contest must not equal the start time of the next contest.

Input

The first line gives NN. (1≤N≤3×1051 \le N \le 3\times10^5)

The next NN lines give information about the contests. Each line contains SiS_i, EiE_i, CiC_i separated by spaces in that order. This means the ii-th contest starts at time SiS_i, ends at time EiE_i, and has prize money CiC_i. (0≤Si<Ei≤1090 \le S_i < E_i \le 10^9, 1≤Ci≤1031 \le C_i \le 10^3)

Output

Print the maximum prize money Seungmin can receive.

Examples2

  1. Example 1

    Input
    2
0 3 3
3 5 2
    Expected output
    3

  2. Example 2

    Input
    7
1 11 6
6 27 7
21 24 7
21 28 5
24 28 1
25 27 2
27 30 7
    Expected output
    20