城市 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$ 需要 1 升水。如果他喝到了水，他将在经过时间 $T$ 后再次需要 1 升水。换句话说，第 $j$ 名乘客在时刻 $D_j + kT$（$k = 0, 1, 2, \dots$）需要水。这里满足 $1 \le D_j < T$，且所有乘客的 $T$ 值相同。如果乘客需要水时供水机中没有水，该乘客就会下车。如果第 $j$ 名乘客在到达城市 O 之前下车，我们需要退还票价。退款金额为 $C_j$ 日元。

司机也需要水。如果他喝到了水，他将在经过时间 $T$ 后再次需要 1 升水，方式与乘客相同。换句话说，司机在时刻 $kT$（$k = 0, 1, 2, \dots$）需要水。如果司机需要水时供水机中没有水，客车的运行就会停止。

不会有两人在同一时刻需要水。当客车到达城市 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 \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 2\,000, M \le 2\,000$
• 子任务 4 [29 分]：无附加限制

样例

样例输入 1

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

样例输出 1

103

样例输入 2

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

样例输出 2

547

样例输入 3

1000000000000 1 1 1000000 6
999999259244
1 123456789

样例输出 3

333333209997456789