题目描述

在两个房子中间，有 $N$ 个公交站，公交车按照如下方式移动（假设每一辆公交车的移动速度一致）：

• 从起点到第 $1$ 个公交站，用时 $X$ 秒。
• 从第 $i$ 个公交站到第 $i+1$ 个公交站，用时 $T_i​$ 秒。（时间每到 $P_i$​ 的倍数，发车一次）
• 从第 $N$ 个公交站到终点，用时 $Y$ 秒。

询问 $Q$ 次，每次给定出发时间 $q_i$​，求到达时间的最小值。

输入格式

第一行，三个整数 $N, X, Y$。$2≤N≤10^5$，$1≤X,Y≤10^9$。

接下来 $N-1$ 行，每行两个整数 $P_i, T_i$。

第 $N+1$ 行，一个整数 $Q$，表示询问次数。$1≤P_i​≤8$，$1≤T_i​≤10^9$。

接下来 $Q$ 行，每行一个整数 $q_i$。$1≤Q≤2×10^5$，$0≤q_i​≤10^9$。

输出格式

共 $Q$ 行，每行一个整数，表示第 $i$ 次询问的到达时间的最小值。

4 2 3
5 4
6 6
3 1
7
13
0
710511029
136397527
763027379
644706927
447672230

34
22
710511052
136397548
763027402
644706946
447672250