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

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

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

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

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

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

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

输入格式

第一行有五个整数 $X,N,M,W,T$。

在接下来的 $N$ 行中，第 $i$ 行有一个整数 $S_i$。

在接下来的 $M$ 行中，第 $j$ 行有两个整数 $D_j,C_j$。

输出格式

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

样例一

input

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

output

103

explanation

• 出发时装了 $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$，车到达终点，总计花销为 $8\times (7+4)+(10+5)=103$，可以证明这是最小花销。

样例二

input

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

output

547

样例三

input

1000000000000 1 1 1000000 6
999999259244
1 123456789

output

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)$。保证 $D_j$ 两两不同。

时间限制：$2\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$