schedule

Problem Description

It would be conceited to presume that you can escape Hell alone. Fortunately, people - or rather, souls - are abundant in Hell, to say the least. Unfortunately, all these tormented souls are hidden behind the forbidding Gates of Hell.

As a super-global economy, however, Hell needs a stable source of income. On an irregular basis, batches of chain-bound souls are marched out of the Gates of Hell and paraded though treacherous terrain on so-called Expeditions to mine Plain Ol' Rock which would be packaged in brightly-coloured wrapping paper and exported as luxury goods at exorbitantly high prices.

Due to the never-ending supply of sinful souls, each Expedition is led only by a small handful of demons which can be effortlessly neutralised by your trusty sword. For each Expedition, the entire time-critical process of travel, scouting and combat can be most elegantly expressed as a mission M_i lasting from day s_i to day e_i that would add n_i souls to your crew.

You can only carry out one mission at any one time and can only gain souls by carrying out missions in their entirety. If a mission starts on the same day that another mission ends, you cannot carry both out.

Find the maximum number of souls you can possibly enslave rally under your cause.

Input

The first line of the input contains an integer N (1 ≤ N ≤ 1000000) indicating the number of missions.

The next N lines each contain 3 integers: s_i (1 ≤ s_i ≤ 1000000), e_i (s_i < e_i ≤ 1000000) and n_i (1 ≤ n_i ≤ 10000)

Output

The output should contain a single integer denoting the maximum number of souls you can attain.

Subtasks

Subtask 1 (5%): n_i = 100

Subtask 2 (15%): N ≤ 18; No restrictions on n_i

Subtask 3 (25%): N ≤ 1000

Subtask 4 (55%): No restrictions

Subtask 5 (0%): Sample input

Sample Input

3
4 10 200
1 3 100
2 9 600

Sample Output

600

Sample Output Explanation

You can attain the maximum number of souls by carrying out the third mission and forgoing the other two.