P6168 [IOI 2016] railroad

Anna works in an amusement park. She is responsible for building a new roller coaster track. She has designed $n$ special segments (for convenience labeled from $0$ to $n-1$) that affect the speed of the roller coaster. Now Anna must connect these special segments together and produce a final roller coaster design. To simplify the problem, you may assume the roller coaster has zero length. For each $i$ between $0$ and $n-1$, special segment $i$ has the following two properties: - When entering this segment, there is a speed limit: the roller coaster’s speed must be less than or equal to $s_i$ $\text{km/h}$ (kilometers per hour). - When leaving this segment, the roller coaster’s speed is exactly $t_i$ $\text{km/h}$, regardless of the speed at which it entered the segment. The final roller coaster design is a single track line that contains these $n$ special segments in some order. Each of the $n$ segments must be used exactly once. Consecutive segments are connected by ordinary track. Anna should choose the order of the $n$ segments, and then determine the length of each connecting track. Track length is measured in meters and can be any non-negative integer (it can be $0$). Each $1$ meter of track between two special segments can slow the roller coaster down by $1$ $\text{km/h}$. At the start of the roller coaster track, when the roller coaster enters the first special segment (according to Anna’s chosen order), its speed is $1$ $\text{km/h}$. The final design must also satisfy: - When entering each special segment, the roller coaster must not violate any speed limit. - The roller coaster’s speed is positive at all times. Your task is to find the minimum possible total length of all connecting tracks (the minimum total length of track between the special segments). If $m=0$, you only need to check whether there exists a valid roller coaster design such that the length of every connecting track is $0$. **Example** ``` 4 1 1 7 4 3 5 8 6 6 ``` In this example, there are $4$ special segments. The best solution is to build them in the order $0,3,1,2$, with connecting track lengths $1,2,0$. The following describes how the roller coaster moves along the track: - Initially, the roller coaster’s speed is $1$ km/h. - The roller coaster starts by entering segment $0$. - The roller coaster leaves segment $0$ at speed $7$ $\text{km/h}$. - Then there is a $1$ $\text{m}$ long piece of track. When the roller coaster reaches the end of this track, its speed is $6$ $\text{km/h}$. - The roller coaster enters segment $3$ at speed $6$ $\text{km/h}$ and leaves it at the same speed. - After leaving segment $3$, the roller coaster travels along a $2$ $\text{m}$ long piece of track. The speed decreases to $4$ $\text{km/h}$. - The roller coaster enters segment $1$ at speed $4$ $\text{km/h}$ and leaves it at speed $3$ $\text{km/h}$. - After leaving segment $1$, the roller coaster immediately enters segment $2$. - The roller coaster leaves segment $2$. Its final speed is $8$ $\text{km/h}$. Total length of track between segments: $1+2+0=3$.

- The first line: two integers $n$ and $m$, where $m=0$ means that if the answer is not $0$, you may return any positive integer, and $m=1$ means you must return the correct answer. - The next $n$ lines: on line $i$, two integers represent $s_{i-1}$ and $t_{i-1}$.

One line: the minimum possible total length of all connecting tracks. (When $m=0$, if there exists a valid roller coaster design such that every connecting track has length $0$, then output $0$; if such a design does not exist, output any positive integer.)

For $100\%$ of the testdata, $1 \le n \le 2 \times {10}^5$, $1 \le s_i \le 10^9$, $1 \le t_i \le 10^9$. Translated by ChatGPT 5