Preventing Robberies

There are n robbers. The i-th robber can choose exactly one time segment to commit his robbery from the list of segments:

\( [a_i, a_i+1], [a_i+1, a_i+2], ..., [b_i-1, b_i] \)

When robber i robs, he plans to steal \( c_i \) money.

You act as a security guard. However, in each 1-length time segment you can stop at most one robber. Note that a robber will choose a time segment that is not guarded if possible. Hence, to catch a robber, you must guard every 1-length segment in his available time range, i.e. all integer time slots from \( a_i \) to \( b_i - 1 \). In other words, if you decide to catch robber i, you commit to guarding every integer time point \( t \) with \( a_i \le t \le b_i - 1 \). Since you can only cover one robbery in each time slot, the chosen robbers must have non-overlapping required time slots.

Your task is to select a subset of robbers such that for every integer time slot, at most one robber’s guarding requirement covers that slot, and the sum of \( c_i \) (the money that would be stolen) of these robbed robbers is maximized. This maximum sum is the amount of loss you can prevent.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of robbers.

Then follow n lines, each containing three integers: a_i, b_i and c_i (1 ≤ a_i < b_i ≤ 10⁹, 1 ≤ c_i ≤ 10⁹), describing the time range and the amount the i-th robber plans to steal.

outputFormat

Output a single integer, the maximum total amount of money you can prevent from being stolen.

sample

3
1 2 100
2 3 200
1 3 250

300