P7480 Reboot from Blue.

YSGHYYDS.

There are $n$ gas stations on a number line. The $i$-th station is at position $x_i$, and its price is $c_i$ yuan per liter. At the beginning, YSGH and his car are at position $s$, and he wants to go to position $t$ ($s < t$). The fuel tank is empty at the start, and it is guaranteed that there is a gas station at position $s$. Assume the car’s fuel tank capacity is unlimited, and $1$ liter of fuel can travel a distance of $1$. He wants to know the minimum cost he needs to pay.

The first line contains three integers $n, s, t$, with the same meaning as in the statement. The next $n$ lines each contain two integers $c_i, x_i$, representing the price and position of the $i$-th gas station, respectively.

Only one line, containing one integer, which is the answer.

**Sample Explanation** The optimal plan is to buy $1$ liter of fuel at the first gas station to reach the second gas station. Buy $3$ liters at the second gas station to reach the third gas station. Buy $3$ liters at the third gas station to reach the destination. The answer is $10 + 2 \times 3 + 1 \times 3 = 19$. --- **Constraints** **This problem uses bundled testdata.** For $100\%$ of the testdata, $1 \le n \le {10}^5$, $-{10}^9 \le x_i, s, t \le {10}^9$, $1 \le c_i \le {10}^9$, $s < t$, and it is guaranteed that there is a gas station at position $s$. - Subtask 1 (10 points): $n \le 20$. - Subtask 2 (30 points): $n \le 5000$. - Subtask 3 (20 points): $c_i$ is uniformly random in $[1, {10}^9]$. - Subtask 4 (40 points): No special constraints. Translated by ChatGPT 5