该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

数轴上分布着 $n$ 个加油站，第 $i$ 个加油站位于坐标 $x_i$ 处，油价为每升 $c_i$ 元。

小远驾驶汽车从坐标 $s$ 出发，前往坐标 $t$（已知 $s < t$）。汽车的油箱初始时是空的，且保证坐标 $s$ 处有一个加油站。

假设汽车的油箱容量没有限制，每升汽油可以行驶 1 个单位距离。

小远想知道，从 $s$ 到达 $t$ 所需的最小加油费用是多少。

输入格式

第一行包含三个整数 $n, s, t$，含义如题面所述。

接下来 $n$ 行，每行包含两个整数 $c_i, x_i$，分别表示第 $i$ 个加油站的油价和所在坐标。

输出格式

仅一行，一个整数，表示最小加油费用。

3 5 10
10 5
2 4
1 7

19

提示

【样例解释】

最优方案是：

• 在第一个加油站（坐标5）加1升油，足以行驶到第二个加油站（坐标4到5距离为1）。
• 在第二个加油站（坐标4）加3升油，足以行驶到第三个加油站（坐标4到7距离为3）。
• 在第三个加油站（坐标7）加3升油，足以行驶到终点（坐标7到10距离为3）。

总费用为 $10×1 + 2×3 + 1×3 = 19$。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据，$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$，且保证坐标 $s$ 处有加油站。

• Subtask 1（10 points）：$n \le 20$。
• Subtask 2（30 points）：$n \le 5000$。
• Subtask 3（20 points）：$c_i$ 在 $[1, 10^9]$ 范围内等概率随机。
• Subtask 4（40 points）：无特殊限制。