Roller Coaster Railroad

Anna works at an amusement park and is in charge of building the railroad for a new roller coaster. She has already designed $n$ special sections, numbered from 0 to $n - 1$, that affect the speed of the roller coaster train. She now has to join them into a final design of the roller coaster. For this problem, the length of the train is zero.

For each $i$ with $0 \le i \le n - 1$, special section $i$ has two properties:

1. When entering the section, there is a speed limit: the speed of the train must be less than or equal to $s_i$ km/h.
2. 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 $n$ special sections in some order. Each of the $n$ sections must be used exactly once. Consecutive sections are connected with tracks. Anna chooses the order of the $n$ sections, then decides the lengths of the tracks. A track length is measured in meters and may be any non-negative integer, including zero. Each meter of track between two special sections slows the train down by 1 km/h. At the start of the ride, the train enters the first special section in the chosen order at 1 km/h.

The final design must satisfy the following:

• The train does not violate any speed limit when entering a special section.
• The speed of the train is positive at all times.

In all subtasks except subtask 3, find the minimum possible total length of track between sections. In subtask 3, only check whether a valid design exists in which every track has zero length.

In all subtasks, $1 \le s_i \le 10^9$ and $1 \le t_i \le 10^9$.