/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 450 点
問題文
高橋君ははじめ高橋君の家におり、これから青木君の家に遊びに行きます。
2 人の家の間には 1 から N までの番号がつけられた N 個のバス停があり、高橋君はそれらの間を下記の方法で移動できます。
- 高橋君の家からバス停 1 まで X だけの時間をかけて徒歩で移動できます。
- 各 i = 1, 2, \ldots, N-1 について、バス停 i からは P_i の倍数である時刻それぞれにバスが出発し、そのバスに乗ることで T_i だけの時間をかけてバス停 (i+1) に移動できます。ここで、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
1 番目のクエリについて、高橋君は下記の通りに移動を行って、時刻 34 に青木君の家に到着することができます。
- 時刻 13 に高橋君の家を出発する。
- 高橋君の家から徒歩で移動し、時刻 15 にバス停 1 に到着する。
- 時刻 15 にバス停 1 を出発するバスに乗り、時刻 19 にバス停 2 に到着する。
- 時刻 24 にバス停 2 を出発するバスに乗り、時刻 30 にバス停 3 に到着する。
- 時刻 30 にバス停 3 を出発するバスに乗り、時刻 31 にバス停 4 に到着する。
- バス停 4 から徒歩で移動し、時刻 34 に青木君の家に到着する。
2 番目のクエリについて、高橋君は下記の通りに移動を行って、時刻 22 に青木君の家に到着することができます。
- 時刻 0 に高橋君の家を出発する。
- 高橋君の家から徒歩で移動し、時刻 2 にバス停 1 に到着する。
- 時刻 5 にバス停 1 を出発するバスに乗り、時刻 9 にバス停 2 に到着する。
- 時刻 12 にバス停 2 を出発するバスに乗り、時刻 18 にバス停 3 に到着する。
- 時刻 18 にバス停 3 を出発するバスに乗り、時刻 19 にバス停 4 に到着する。
- バス停 4 から徒歩で移動し、時刻 22 に青木君の家に到着する。
Score : 450 points
Problem Statement
Takahashi is initially at his house and is about to visit Aoki's house.
There are N bus stops numbered 1 to N between the two houses, and Takahashi can move between them in the following ways:
- He can walk from his house to bus stop 1 in X units of time.
- For each i = 1, 2, \ldots, N-1, a bus departs from bus stop i at each time that is a multiple of P_i, and by taking this bus, he can get to bus stop (i+1) in T_i units of time. Here, the constraints guarantee that 1 \leq P_i \leq 8.
- Takahashi can walk from bus stop N to Aoki's house in Y units of time.
For each i = 1, 2, \ldots, Q, process the following query.
Find the earliest time that Takahashi can arrive at Aoki's house when he leaves his house at time q_i.
Note that if he arrives at a bus stop exactly at the departure time of a bus, he can take that bus.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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
Output
Print Q lines. For each i = 1, 2, \ldots, Q, the i-th line should contain the answer to the i-th query.
Sample Input 1
4 2 3 5 4 6 6 3 1 7 13 0 710511029 136397527 763027379 644706927 447672230
Sample Output 1
34 22 710511052 136397548 763027402 644706946 447672250
For the first query, Takahashi can move as follows to arrive at Aoki's house at time 34.
- Leave his house at time 13.
- Walk from his house and arrive at bus stop 1 at time 15.
- Take the bus departing from bus stop 1 at time 15 and arrive at bus stop 2 at time 19.
- Take the bus departing from bus stop 2 at time 24 and arrive at bus stop 3 at time 30.
- Take the bus departing from bus stop 3 at time 30 and arrive at bus stop 4 at time 31.
- Walk from bus stop 4 and arrive at Aoki's house at time 34.
For the second query, Takahashi can move as follows and arrive at Aoki's house at time 22.
- Leave his house at time 0.
- Walk from his house and arrive at bus stop 1 at time 2.
- Take the bus departing from bus stop 1 at time 5 and arrive at bus stop 2 at time 9.
- Take the bus departing from bus stop 2 at time 12 and arrive at bus stop 3 at time 18.
- Take the bus departing from bus stop 3 at time 18 and arrive at bus stop 4 at time 19.
- Walk from bus stop 4 and arrive at Aoki's house at time 22.