题目描述

在城市 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$。

输出格式

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

19 1 4 8 7
10
1 20
2 10
4 5
6 5

103

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

547

1000000000000 1 1 1000000 6
999999259244
1 123456789

333333209997456789

提示

样例 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 完成