P7480 Reboot from Blue

YSGHYYDS

数轴上有 $n$ 个加油站，第 $i$ 个位于 $x_i$，油价是每升 $c_i$ 元。 YSGH 和他的车一开始位于坐标 $s$，它想去坐标 $t$（$s < t$），车的油箱一开始是空的，保证坐标 $s$ 有加油站。 假设车的油箱容量无限大，一升油能走距离 $1$。 他想知道他需要花费的最小费用。

无

无

**【样例解释】** 最优方案是在第一个加油站加 $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）：无特殊限制。