長距離バス (Long Distance Coach)
题意翻译
#「JOISC 2017 Day 3」长途巴士
## 题目描述
**题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day3 T1「[長距離バス](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d3.pdf)（[Long Distance Coach](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d3-en.pdf)）」**
某长途巴士发车时刻为 $0$，到达终点的时刻为 $X$。车上装有饮水机，乘客和司机可以在车上装水喝。出发前水箱是满的。
途中有 $N$ 个服务站，依次编号为 $1\ldots N$。巴士到达服务站 $i(1\le i\le N)$ 的时间是 $S_i$。保证 $S_1,S_2,\ldots,S_N$ 严格递增。
在服务站可以给饮水机加水，但是要钱，水价为每升 $W$ 円。
本次巴士有 $M$ 名乘客（不含司机），乘客 $j(1\le j\le M)$ 在时刻 $kT+D_j(k=0,1,2,\ldots)$ 需要装 $1$ 升水，在其他时刻不装水。保证 $1≤ D_j < T$。
司机在时刻 $kT(k=0,1,2,\ldots)$ 需要装 $1$ 升水，在其他时刻不装水。如果某一名乘客想装水时饮水机没水了，这名乘客会怒而下车，此时需要向这名乘客退 $C_j$ 円。如果司机想装水时没水了，司机会怒而下车，这车就不开了。
**保证不会出现两人在同一时刻需要装水的情况**。在服务站或是到达终点时，如果司机或乘客要喝水，他们会在站里装水，而非在车上装水。
我们希望花销（买水的总费用 $+$ 退的所有车费）尽可能小。试求至少需要花销多少円。
## 输入格式
第一行有 5 个整数 $X, N, M, W, T$。
在接下来的 $N$ 行中，第 $i$ 行有一个整数 $S_i$。
在接下来的 $M$ 行中，第 $j$ 行有两个整数 $D_j, C_j$。
## 输出格式
一行，一个整数，表示至少需要花销多少円。
## 样例
#### 样例输入 1
```plain
19 1 4 8 7
10
1 20
2 10
4 5
6 5
```
#### 样例输出 1
```plain
103
```
#### 样例解释 1
* 出发时装了 7 升水。
* 在时刻 $0, 1, 2, 4, 6$，司机与乘客 $1, 2, 3, 4$ 先后装水。
#### 样例输入 2
```plain
105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35
```
#### 样例输出 2
```plain
547
```
#### 样例输入 3
```plain
1000000000000 1 1 1000000 6
999999259244
1 123456789
```
#### 样例输出 3
```plain
333333209997456789
```
## 限制与提示
对于所有数据，$1\le T\le X\le 10^{12}, 1\le N, M \le 2\times 10^5,$ $1\le W\le 10^6,$ $1\le S_i< X(1\le i\le N),$ $1\le D_j < T, $ $1\le C_j\le 10^9(1\le j\le M)$。
|子任务|分值|$N,M$|
|-|-|-|
|1|16|$N,M\le 8$|
|2|30|$N,M\le 100$|
|3|25|$N,M\le 2000$|
|4|29|$N,M\le 2\times 10^5$|
感谢 Planet6174 提供的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/joisc2017/tasks/joisc2017_g