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
3 4 10 200 1 3 100 2 9 600
You can attain the maximum number of souls by carrying out the third mission and forgoing the other two.