P14388 [JOISC 2017] 长途巴士 / Long Distance Coach

在城市 I 与城市 O 之间有一辆长途客车，车上配备了一台供水机，乘客和司机均可从中取水饮用。客车于时间 $0$ 从城市 I 出发，于时间 $X$ 抵达城市 O。沿途共有 $N$ 个补水点，客车在第 $i$ 个补水点（$1 \le i \le N$）的到达时间为 $S_i$。 初始时，供水机内无水。我们可以在出发前向供水机注水；此外，当客车停靠在补水点时，也可向供水机注水。无论客车处于何处，每升水的价格均为 $W$ 日元。 在城市 I，有 $M$ 名乘客上车，乘客编号为 $1$ 至 $M$。除城市 I 外，其他地点无乘客上车。第 $j$ 名乘客（$1 \le j \le M$）在时间 $D_j$ 需要一升水。若他饮水，则在经过时间 $T$ 后将再次需要一升水。换言之，第 $j$ 名乘客在时间 $D_j + kT$（$k = 0, 1, 2, \ldots$）需要水。此处满足 $1 \le D_j < T$，且所有乘客的 $T$ 值相同。若供水机在乘客需要水时无水，则该乘客将离开客车。若第 $j$ 名乘客在抵达城市 O 前离开客车，我们需要退还其车费，退款费用为 $C_j$ 日元。 司机同样需要饮水。若他饮水，则在经过时间 $T$ 后将再次需要一升水，方式与乘客相同。换言之，司机在时间 $kT$（$k = 0, 1, 2, \ldots$）需要水。若供水机在司机需要水时无水，则客车运营将停止。 不会同时有两人需要水。当客车抵达城市 O 或补水点时，乘客和司机均不需要水。 通过调整在补水点向供水机注水的水量，我们希望最小化水费与退款费用之和，并确保客车能够顺利运营至城市 O。你的任务是决定在旅途中于何处、注入多少水量至供水机。 **任务** 给定客车的行驶时间、补水点信息、乘客与司机的需求信息，编写一个程序，计算在客车成功抵达城市 O 的前提下，水费与退款费用之和的最小值。

从标准输入读取以下数据： - 输入的第一行包含五个以空格分隔的整数 $X$、$N$、$M$、$W$、$T$。这表示客车将在时间 $X$ 抵达城市 O，沿途有 $N$ 个补水点，车上共有 $M$ 名乘客，每升水的价格为 $W$ 日元，乘客与司机的饮水间隔时间为 $T$。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $S_i$，表示客车将在时间 $S_i$ 到达第 $i$ 个补水点。 - 接下来的 $M$ 行中，第 $j$ 行（$1 \le j \le M$）包含两个以空格分隔的整数 $D_j$、$C_j$，表示第 $j$ 名乘客首次需要水的时间为 $D_j$，且为其退款的费用为 $C_j$。

向标准输出写入一行。输出包含一个整数，表示最小总费用。

### 样例 1 解释 在本样例输入中，若我们在出发前向供水机注入 7 升水，并在第一个补水点注入 4 升水，则客车的运行过程如下： 1. 客车从城市 I 出发。此时，供水机内有 7 升水。 2. 司机与乘客 1、2、3、4 分别在时间 $0$、$1$、$2$、$4$、$6$ 饮用 1 升水。剩余水量为 2 升。 3. 司机与乘客 1 分别在时间 $7$、$8$ 饮用 1 升水。剩余水量为 0 升。 4. 在时间 $9$，乘客 2 需要水，但由于供水机无水，他离开客车。 5. 在时间 $10$，我们在第一个补水点向供水机注入 4 升水。剩余水量为 4 升。 6. 乘客 3、4、司机与乘客 1 分别在时间 $11$、$13$、$14$、$15$ 饮用 1 升水。剩余水量为 0 升。 7. 在时间 $18$，乘客 3 需要水，但由于供水机无水，他离开客车。 8. 在时间 $19$，客车抵达城市 O。 总共用水量为 11 升，水费为 88 日元。乘客 2 与乘客 3 的退款费用之和为 15 日元。总费用为 103 日元。 我们输出 103，因为若总费用小于或等于 102 日元，则无法使客车正常运行。 ### 数据范围 所有输入数据均满足以下条件： - $1 \le X \le 1\,000\,000\,000\,000$。 - $1 \le N \le 200\,000$。 - $1 \le M \le 200\,000$。 - $1 \le W \le 1\,000\,000$。 - $1 \le T \le X$。 - $1 \le S_i < X$（$1 \le i \le N$）。 - $1 \le D_j < T$（$1 \le j \le M$）。 - $1 \le C_j \le 1\,000\,000\,000$（$1 \le j \le M$）。 - $D_j$（$1 \le j \le M$）互不相同。 - 当客车抵达城市 O 或补水点时，乘客与司机均不需要水。 ### 子任务 共有 4 个子任务。每个子任务的得分及额外约束如下： **子任务 1 [16 分]** - $N \le 8$。 - $M \le 8$。 **子任务 2 [30 分]** - $N \le 100$。 - $M \le 100$。 **子任务 3 [25 分]** - $N \le 2000$。 - $M \le 2000$。 **子任务 4 [29 分]** 无额外约束。 翻译由 Qwen3-235B 完成