题目描述

题目译自 JOISC 2024 Day3 T3 「塔 / Tower」

IOI 塔是一座极高的塔，塔上设有登塔楼梯。楼梯有 $10^{100}$ 级，从下到上按第 $0$ 级，第 $1$ 级依次编号。JOI 君目前在第 $0$ 级，并且想要爬上楼梯。JOI 君可以按如下两种方式爬楼梯。不可以走下楼梯。

上一级楼梯。这个操作花费 $A$ 秒。

从目前的一级楼梯跳到它上面 $D$ 级楼梯，跳过中间的楼梯。这个操作花费 $B$ 秒。

目前，楼梯的某些地方正在施工，正在施工的楼梯不能踩上去。更确切地说，有 $N$ 处在施工的地方，第 $i$ 处为第 $L_i, L_i+1, \ldots, R_i$ 级台阶。

IOI 塔有 $Q$ 个房间，编号为 $1$ 到 $Q$。可以从第 $X_j\ (1\le j\le Q)$ 级台阶进入房间 $j$。因此，JOI 君想确定他是否可以到达每个房间，如果可以，他想知道到达那个房间最少要花多长时间。

给定 JOI 君，施工和房间的信息，写一个程序判断 JOI 君是否能到达每个房间 $X_j$，如果可以，计算到达房间的最短时间。

输入格式

第一行两个整数 $N, Q$。

第二行三个整数 $D, A, B$。

接下来 $N$ 行，每行两个整数 $L_i, R_i$。

接下来 $Q$ 行，每行一个整数 $X_j$。

输出格式

输出 $Q$ 行，第 $j$ 行输出如果 JOI 君能够到达 $X_j$ 的话，所需的最短用时，否则输出 $-1$。

样例1：

3 1
4 10 35
4 5
10 12
14 14
13

120

JOI 君可以通过如下方式，花 $120$ 秒到达第 $13$ 级台阶：

从台阶 $0$ 走到台阶 $1$，花费 $10$ 秒。

从台阶 $1$ 走到台阶 $2$，花费 $10$ 秒。

从台阶 $2$ 走到台阶 $3$，花费 $10$ 秒。

从台阶 $3$ 跳到台阶 $7$，花费 $35$ 秒。

从台阶 $7$ 走到台阶 $8$，花费 $10$ 秒。

从台阶 $8$ 走到台阶 $9$，花费 $10$ 秒。

从台阶 $9$ 跳到台阶 $13$，花费 $35$ 秒。

因为不可能花费小于 $120$ 秒到达台阶 $13$，所以输出 $120$。

这组样例满足子任务 $1, 2, 4$ 的限制。

样例2：

5 10
10 1 9
7 11
25 32
37 38
43 44
50 52
6
12
18
24
30
36
42
48
54
60

6
11
17
22
-1
33
-1
44
-1
55

这组样例满足子任务 $1, 2, 4$ 的限制。

数据规模与约定

$1 \le N, Q \le 2 \times 10^5$

$1 \le D \le 10^{12}$

$1 \le A, B \le 10^6$

$1 \le L_i \le R_i \le 10^{12} \ (1 \le i \le N)$

$R_i + 1 < L_{i+1} \ (1 \le i \le N - 1)$

$1 \le X_j \le 10^{12} \ (1 \le j \le Q)$

详细子任务附加限制及说明如下表所示。

$子任务编号$	$附加限制$	$分值$
$1$	$R_i, X_j \le 10^6$	$5$
$2$	$N, Q \le 2,000$	$38$
$3$	$A = 1, B = D$	$25$
$4$	$无附加限制$	$32$