In Nlogonia, the construction of the long-awaited Tall And Prestigious tower (TAP) has finally begun. The scaffolding that will be used by the workers in the various operations required to carry out this monumental work is already installed and ready for use. Each scaffolding can be modeled as a horizontal segment (i.e., aligned with the $$$x$$$-axis). The $$$i$$$-th scaffolding is located at a height $$$H_i$$$ above the ground and, and covers the coordinates on the $$$x$$$ axis between $$$L_i$$$ and $$$R_i$$$ inclusive.
However, the placement of the stairs that will serve for the access of the workers and transportation of materials has not yet been determined. For this reason, we have been hired to carry out this important task. Each staircase can be modeled as a segment with an upper and lower end. We call the lower end of a staircase its base. The bases of the stairs can be supported on the ground or on a scaffolding, and their upper ends must be supported on another scaffolding.
Furthermore, in order for them to be functional, the stairs must be constructed in such a way that it is possible to access from the ground (modeled by the $$$x$$$-axis, at height $$$0$$$) to any of the scaffolding, going up and down as many stairs as necessary. Since the stairs are intended to be used for carrying heavy objects, it was decided that they should be installed at a $$$45^{\circ}$$$ angle, so that if a staircase has the upper end at a height $$$D$$$ meters above its base, its upper end will have an $$$x$$$ coordinate that is $$$D$$$ meters to the left or right of the $$$x$$$ coordinate of its base.
It is possible to install the stairs in such a way that their segments intersect, but for safety reasons it is strictly forbidden to move from one staircase to another outside of a scaffolding. In other words, a staircase only connects the scaffolding on which its ends are supported (or the ground with a scaffolding, in the case of stairs with a base on the ground).
Since the company wants to save costs, they have asked us to determine the minimum total cost of installing all the necessary stairs, taking into account that the cost of a staircase is equal to the difference between the height of its upper end and the height of its base.
The first line contains a single integer $$$N$$$ $$$(1 \leq N \leq 10^5)$$$, the number of scaffolding installed in the TPT. The following $$$N$$$ lines contain $$$3$$$ integers $$$H_i$$$, $$$L_i$$$, and $$$R_i$$$ $$$(1 \leq H_i \leq 10^9, -10^9 \leq L_i < R_i \leq 10^9)$$$, where $$$H_i$$$ is the height of the $$$i$$$-th scaffolding, while $$$L_i$$$ and $$$R_i$$$ are the positions of the left and right ends of the scaffolding, respectively. It is guaranteed that the scaffolding do not share any points.
A single line with an integer equal to the minimum total cost of installing all the stairs.
7 2 -2 0 3 -1 1 3 2 3 4 -2 1 4 2 3 2 1 2 1 4 5
8
One way to obtain the result of the example can be found in the image in the problem statement, using $$$6$$$ stairs with a cost of $$$1$$$, and one staircase with a cost of $$$2$$$. Note that in this solution, the stairs with a base on scaffolding located at a height of $$$3$$$ are not connected to each other.
