Description

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.

Input Format

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.

Output Format

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

3 5 10
10 5
2 4
1 7

19

Hint

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