该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

某长途巴士发车时刻为 $0$，到达终点的时刻为 $X$。车上装有饮水机，乘客和司机可以在车上装水喝。

途中有 $N$ 个服务站，依次编号为 $1 \dots N$。巴士到达服务站 $i (1 \leq i \leq N)$ 的时间是 $S_i$。

发车前，水箱是空的。在发车前你可以给饮水机加水，在服务站时也可以给饮水机加水，但是都要钱，水价为每升 $W$ 元。假设水箱容量无限。

本次巴士有 $M$ 名乘客（不含司机），乘客均在起点上车，不会中途下车。乘客 $j (1 \leq j \leq M)$ 在时刻 $kT + D_j (k = 0, 1, 2, \dots)$ 需要装 $1$ 升水，在其他时刻不装水。保证 $1 \leq D_j < T$。

司机在时刻 $kT (k = 0, 1, 2, \dots)$ 需要装 $1$ 升水，在其他时刻不装水。如果到终点之前，某一名乘客想装水时饮水机没水了，这名乘客会怒而下车，此时需要向这名乘客退 $C_j$ 元。如果到终点之前，司机想装水时没水了，司机会怒而下车，这车就不开了。

保证不会出现两人在同一时刻需要装水的情况。保证在服务站或是到达终点时，不存在司机或乘客需要喝水。

我们希望花销（买水的总费用与退的所有车费之和）尽可能小，并且把车开到终点。试求至少需要花销多少元。

输入格式

从 water.in 中读取数据。

输入的第一行为 $X, N, M, W, T$。

接下来 $N$ 行，每行一个整数 $S_i$。

接下来 $M$ 行，每行两个整数 $D_j, C_j$。

输出格式

向 water.out 中输出写入一行。

输出包含一个整数，表示最小总费用。

输入输出样例 #1

输入 #1

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

输出 #1

103

输入输出样例 #2

输入 #2

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

输出 #2

547

输入输出样例 #3

输入 #3

1000000000000 1 1 1000000 6
999999259244
1 123456789

输出 #3

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 或补水点时，乘客与司机均不需要水。