长途巴士

题号：NC53228
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2017 Day3 T1「長距離バス / Long Distance Coach」

某长途巴士发车时刻为0，到达终点的时刻为X。车上装有饮水机，乘客和司机可以在车上装水喝。
途中有N个服务站，依次编号为 $1 \ldots N$ 。巴士到达服务站 $i(1 \le i \le N)$ 的时间是 $S_i$ 。
发车前，水箱是空的。在发车前你可以给饮水机加水，在服务站时也可以给饮水机加水，但是都要钱，水价为每升W円。假设水箱容量无限。
本次巴士有M名乘客（不含司机），乘客均在起点上车，不会中途下车。乘客 $j(1 \le j \le M)$ 在时刻 $kT+D_j(k=0,1,2, \ldots )$ 需要装1升水，在其他时刻不装水。保证 $1≤D_j\lt T$ 。
司机在时刻 $kT(k=0,1,2, \ldots )$ 需要装1升水，在其他时刻不装水。如果到终点之前，某一名乘客想装水时饮水机没水了，这名乘客会怒而下车，此时需要向这名乘客退 $C_j$ 円。如果到终点之前，司机想装水时没水了，司机会怒而下车，这车就不开了。
保证不会出现两人在同一时刻需要装水的情况。保证在服务站或是到达终点时，不存在司机或乘客需要喝水。
我们希望花销（买水的总费用与退的所有车费之和）尽可能小，并且把车开到终点。试求至少需要花销多少円。

输入描述:

第一行有五个整数X,N,M,W,T。
在接下来的N行中，第i行有一个整数。在接下来的M行中，第j行有两个整数。

输出描述:

一行，一个整数，表示最少的花销。

示例1

输入

复制

输出

复制

说明

出发时装了7升水；
在时刻0,1,2,4,6，司机与乘客1,2,3,4先后装水，饮水机剩2升水；
在时刻7,8，司机和乘客1先后装水，饮水机没水了；
在时刻9，乘客2需要装水，但是饮水机没水了，因此乘客2下车，需要向其退款；
在时刻10，车到了服务站，向饮水机加4升水，此时饮水机剩余4升水；
在时刻11,13,14,15，乘客3,4，司机和乘客1先后装水，饮水机没水了；
在时刻18，乘客3需要装水，但是饮水机没水了，因此乘客3下车，需要向其退款；
在时刻19，车到达终点，总计花销为，可以证明这是最小花销。

示例2

输入

复制

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35

输出

复制

示例3

输入

复制

1000000000000 1 1 1000000 6
999999259244
1 123456789

输出

复制

333333209997456789

备注:

对于所有数据，。保证两两不同。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2396