Roller Coaster Railroad#7976
Anna is working in an amusement park and she is in charge of building the railroad for a new roller coaster. She has already designed special sections (conveniently numbered from to n - 1 that affect the speed of a roller coaster train. She now has to put them together and propose a final design of the roller coaster. For the purpose of this problem you may assume that the length of the train is zero.
For each between and n - 1, inclusive, special section has two properties:
when entering the section, there is a speed limit: the speed of the train must be less or equal to s_i km/h (kilometers per hour),
when leaving the section, the speed of the train is exactly t_i km/h, regardless of the speed at which the train entered the section.
The finished roller coaster is a single railroad line that contains the special sections in some order. Each of the sections should be used exactly once. Consecutive sections are connected with tracks. Anna should choose the order of the sections and then decide the lengths of the tracks. The length of a track is measured in meters and may be equal to any non-negative integer (possibly zero).
Each meter of the track between two special sections slows the train down by km/h. At the beginning of the ride, the train enters the first special section in the order selected by Anna, going at km/h.
The final design must satisfy the following requirements:
the train does not violate any speed limit when entering the special sections;
the speed of the train is positive at any moment.
Your task is to find the minimum possible total length of tracks between sections.
First line contains number n~(2 \le n \le 2 \cdot 10^5). Each of the next lines contains numbers s_i and t_i~(1 \le i \le n, 1 \le s_i, t_i \le 10^9).
Print the minimum possible total length of all tracks between sections.
Example 1
Example 2