附加文件

题目描述

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱里有 $S$ 升汽油，每升汽油能行驶 $1$ 个单位距离）。给定两个城市之间的距离 $L$、汽车油箱的容量 $C$（以升为单位）、沿途油站数 $N$，油站 $i$ 离出发点的距离 $D_i$、每升汽油价格 $P_i$（$i=1,2,…,N$）。每个油站汽油无限。请输出最少费用。如果无法到达目的地，则输出 -1。

输入格式

第一行：四个整数：$N, C, S, L$

接下来 $N$ 行：每行两个整数 $D_i$ 与 $P_i$

输出格式

一个整数，表示最少费用。如果无法到达目的地，则输出 -1。

样例输入

4 10 3 16
2 20
9 15
5 5
10 10

样例输出

100

样例解释

出发时，油箱里有 3 升汽油，他先行驶 2 个单位距离，到达距起点距离为 2 的油站，油箱还剩 1 升汽油，购买 2 升汽油（花费 2×20=40 元）。然后到达距起点距离为 5 的油站，油箱为空，购买 10 升汽油（花费 10×5=50 元），加满油箱。再到达距起点距离为 10 的加油站，油箱还剩 5 升汽油，购买 1 升汽油（花费 1×10=10 元），然后直达目的地。总花费是 40+50+10=100 元。

数据范围

10% 的数据：$1 ≤ N ≤ 5$

20% 的数据：$1 ≤ N ≤ 10$

30% 的数据：$1 ≤ N ≤ 100$

40% 的数据：$1 ≤ N ≤ 1000$

60% 的数据：$1 ≤ N ≤ 5000$

100% 的数据：$1 ≤ N ≤ 5 × 10^4$，$1 ≤ C ≤ 10^6$，$0 ≤ S ≤ L$，$1 ≤ L ≤ 10^9$，$0 ≤ D_i ≤ L$，$1 ≤ P_i ≤ 10^6$