Alien Invasion Defense

The aliens from outer space have (finally!) invaded Earth. Defend yourself, or be disintegrated! Or assimilated. Or eaten. We are not yet sure.

The aliens follow a known attack pattern. There are \(n\) attackers. The \(i\text{-th}\) one appears at time \(a_i\) and is at distance \(d_i\) from you. He must be destroyed no later than time \(b_i\), or else he will fire his weapon, which will definitely end the fight.

Your weapon is an area-blaster, which can be set to any given power. If fired with power \(R\), it momentarily destroys all aliens at distance \(R\) or smaller and consumes \(R\) fuel cells.

Determine the minimal cost (measured in fuel cells) required to destroy all the aliens without being killed.

Note: A single blast can take out multiple aliens if all of them are within range \(R\) and the blast time is chosen such that it falls within their available time window. Formally, if an alien \(i\) is destroyed by a blast fired at time \(t\) with power \(R\), then it must hold that \(a_i \le t \le b_i\) and \(d_i \le R\). The cost of a blast is equal to its power \(R\), so a strategy that minimizes the total cost is required.

inputFormat

The first line contains a single integer \(n\) (the number of aliens). Each of the next \(n\) lines contains three integers \(a_i\), \(b_i\), and \(d_i\):

• \(a_i\): the time the \(i\text{-th}\) alien appears.
• \(b_i\): the time by which the \(i\text{-th}\) alien must be destroyed.
• \(d_i\): the distance of the alien from you.

You may assume that a solution always exists.

outputFormat

Output a single integer: the minimal total fuel cells required to destroy all the aliens.

sample

3
1 5 3
2 6 2
4 7 4

4