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 Mi lasting from day si to day ei that would add ni 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.


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: si (1 ≤ si ≤ 1000000), ei (si < ei ≤ 1000000) and ni (1 ≤ ni ≤ 10000)


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


Subtask 1 (5%): ni = 100

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

Subtask 3 (25%): N ≤ 1000

Subtask 4 (55%): No restrictions

Subtask 5 (0%): Sample input

Sample Input

4 10 200
1 3 100
2 9 600

Sample Output


Sample Output Explanation

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

Submitting .cpp to 'schedule'

You're not logged in! Click here to login

Time Limit: 3 Seconds
Memory Limit: 256MB
Your best score: 0
Source: HCI NOI Selection Test 2014

Subtask Score
1 5
2 15
3 25
4 55
5 0