题目背景

YSGHYYDS

题目描述

数轴上有 $n$ 个加油站，第 $i$ 个位于 $x_i$，油价是每升 $c_i$ 元。

YSGH 和他的车一开始位于坐标 $s$，它想去坐标 $t$（$s < t$），车的油箱一开始是空的，保证坐标 $s$ 有加油站。

假设车的油箱容量无限大，一升油能走距离 $1$。

他想知道他需要花费的最小费用。

输入格式

第一行，三个整数 $n, s, t$，意义同题面描述。

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

输出格式

仅一行，一个整数，表示答案。

3 5 10
10 5
2 4
1 7

19

提示

【样例解释】

最优方案是在第一个加油站加 $1$ 升油到第二个加油站。

在第二个加油站加 $3$ 升油到第三个加油站。

在第三个加油站加 $3$ 升油到终点。

答案是 $10 + 2 \times 3 + 1 \times 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）：无特殊限制。