← 返回题目列表

AtCoder · abc319_e

H. 巴士站

中文机器翻译题面 查看原题

分数: 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.