Bus Stops

题目描述

Takahashi 最初在他家，准备去 Aoki 的家。 在两家之间有编号为 $1$ 到 $N$ 的 $N$ 个公交站，Takahashi 可以通过以下方式在它们之间移动：

他可以在 $X$ 时间单位内从他家步行到公交站 $1$。 对于每个 $i = 1, 2, \ldots, N-1$，在每个是 $P_i$ 的倍数的时间点都会有一辆公交从公交站 $i$ 发车，乘坐这辆公交，他可以在 $T_i$ 时间单位内到达公交站 $(i+1)$。这里，约束保证 $1 \leq P_i \leq 8$。 Takahashi 可以在 $Y$ 时间单位内从公交站 $N$ 步行到 Aoki 的家。

对于每个 $i = 1, 2, \ldots, Q$，处理以下查询。

当他在时间 $q_i$ 离开他家时，找出 Takahashi 可以到达 Aoki 的家的最早时间。

注意如果他恰好在公交发车时间到达公交站，则可以乘坐该班公交。

输入格式

输入由标准输入按以下格式给出： $N$ $X$ $Y$ $P_1$ $T_1$ $P_2$ $T_2$ $\vdots$ $P_{N-1}$ $T_{N-1}$ $Q$ $q_1$ $q_2$ $\vdots$ $q_Q$

输出格式

输出 $Q$ 行。 对于每个 $i = 1, 2, \ldots, Q$，第 $i$ 行应包含第 $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

提示

$2 \leq N \leq 10^5$ $1 \leq X, Y \leq 10^9$ $1 \leq P_i \leq 8$ $1 \leq T_i \leq 10^9$ $1 \leq Q \leq 2 \times 10^5$ $0 \leq q_i \leq 10^9$ 所有输入值都是整数。对于第一个查询，Takahashi 可以按如下方式移动以在时间 $34$ 到达 Aoki 的家。

在时间 $13$ 离开他家。 步行从他家到达公交站 $1$，在时间 $15$ 到达。 乘坐在公交站 $1$ 于时间 $15$ 发车的公交，并在时间 $19$ 到达公交站 $2$。 乘坐在公交站 $2$ 于时间 $24$ 发车的公交，并在时间 $30$ 到达公交站 $3$。 乘坐在公交站 $3$ 于时间 $30$ 发车的公交，并在时间 $31$ 到达公交站 $4$。 从公交站 $4$ 步行并在时间 $34$ 到达 Aoki 的家。

对于第二个查询，Takahashi 可以按如下方式移动并在时间 $22$ 到达 Aoki 的家。

在时间 $0$ 离开他家。 步行从他家到达公交站 $1$，在时间 $2$ 到达。 乘坐在公交站 $1$ 于时间 $5$ 发车的公交，并在时间 $9$ 到达公交站 $2$。 乘坐在公交站 $2$ 于时间 $12$ 发车的公交，并在时间 $18$ 到达公交站 $3$。 乘坐在公交站 $3$ 于时间 $18$ 发车的公交，并在时间 $19$ 到达公交站 $4$。 从公交站 $4$ 步行并在时间 $22$ 到达 Aoki 的家。

标签: AtCoder|abc319E

来源

AtCoder|abc319E