分数: 450 点
问题陈述
高桥最初在他家,并准备去青木家拜访。
有 N 巴士站编号 1 to N 在两栋房子之间,高桥可以通过以下方式在它们之间移动:
- 他可以从家步行到公交车站 1 in X 时间单位。
- 对于每个 i = 1, 2, \ldots, N-1, 巴士从巴士站出发 i 每次都是 P_i,乘坐这辆公交车,他可以到达公交车站 (i+1) in T_i 时间单位。 这里,约束保证 1 \leq P_i \leq 8.
- 高桥可以从公交车站步行 N 去青木家 Y 时间单位。
对于每个 i = 1, 2, \ldots, Q,处理以下查询。
求高桥离开家的时间最早可以到达青木家 q_i.
请注意,如果他恰好在公共汽车的出发时间到达公共汽车站,则他可以乘坐该公共汽车。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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- 第一个查询。
样本输入 1
4 2 3 5 4 6 6 3 1 7 13 0 710511029 136397527 763027379 644706927 447672230
示例输出 1
34 22 710511052 136397548 763027402 644706946 447672250
第一次查询,高桥可以按如下方式移动,到达青木家的时间 34.
- 准时离开家 13.
- 从他家步行到达公交车站 1 时间 15.
- 乘坐巴士从巴士站出发 1 时间 15 并到达巴士站 2 时间 19.
- 乘坐巴士从巴士站出发 2 时间 24 并到达巴士站 3 时间 30.
- 乘坐巴士从巴士站出发 3 时间 30 并到达巴士站 4 时间 31.
- 从公交车站步行 4 并按时到达青木家 34.
第二次查询,高桥可以按如下方式移动,并按时到达青木家 22.
- 准时离开家 0.
- 从他家步行到达公交车站 1 时间 2.
- 乘坐巴士从巴士站出发 1 时间 5 并到达巴士站 2 时间 9.
- 乘坐巴士从巴士站出发 2 时间 12 并到达巴士站 3 时间 18.
- 乘坐巴士从巴士站出发 3 时间 18 并到达巴士站 4 时间 19.
- 从公交车站步行 4 并按时到达青木家 22.