C - Dominoes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、N 個のドミノが一列に並べられたドミノ倒しのコースを作りました。ドミノには左から順に 1 から N までの番号が付けられています。

各ドミノ i（1 \leq i \leq N）には「許容衝撃値」P_i と「衝撃増分」D_i が定められています。許容衝撃値とは、そのドミノが粉砕されずに正常に倒れることのできる衝撃値の上限です。

このコースでは、ドミノ 1 にボールを当てることでドミノ倒しが始まります。ボールを当てたときの初期衝撃値を S とします。ドミノ倒しは、ドミノ 1 から順に以下のように進行します。

ドミノ i に到達した時点での衝撃値を C_i とします。ドミノ 1 については C_1 = S です。

  • C_i \leq P_i の場合（衝撃値が許容衝撃値以下の場合）、ドミノ i は正常に倒れます。i < N のとき、倒れたドミノ i は次のドミノ i+1 に衝撃を伝え、ドミノ i+1 に到達する衝撃値は C_{i+1} = C_i + D_i となります。
  • C_i > P_i の場合（衝撃値が許容衝撃値を超えている場合）、ドミノ i は衝撃に耐えきれず粉砕されます。粉砕されたドミノは倒れることなく砕け散るため、次のドミノに衝撃は伝わらず、ドミノ倒しはそこで終了します。粉砕されたドミノは「正常に倒れた」とはみなしません。

高橋君は Q 回の実験を行います。各実験は互いに独立であり、毎回すべてのドミノが初期配置に戻された上で行われます。各実験 j（1 \leq j \leq Q）では、ドミノ 1 にぶつけるボールの初期衝撃値 S_j が与えられます。

各実験について、正常に倒れた最後のドミノの番号を求めてください。すべてのドミノが正常に倒れた場合は N を出力してください。ドミノ 1 すら正常に倒れなかった場合（すなわち S_j > P_1 であった場合）は 0 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9（1 \leq i \leq N）
  • 0 \leq D_i \leq 10^9（1 \leq i \leq N）
  • 0 \leq S_j \leq 10^9（1 \leq j \leq Q）
  • 入力はすべて整数である。

注意

衝撃値はドミノ倒しの過程で 10^9 を超える場合があります。すべてのドミノが正常に倒れる場合、衝撃値は最大で S_j + D_1 + D_2 + \cdots + D_{N-1} に達する可能性がありますが、これは 64 ビット符号付き整数の範囲に収まります。

D_N は入力として与えられますが、ドミノ N の次のドミノは存在しないため使用されません。

入力

N Q
P_1 D_1
P_2 D_2
\vdots
P_N D_N
S_1
S_2
\vdots
S_Q
  • 第 1 行には、ドミノの個数を表す整数 N と、実験の回数を表す整数 Q が、スペース区切りで与えられる。
  • 第 2 行から第 N + 1 行では、各ドミノの許容衝撃値と衝撃増分が与えられる。
  • 第 i + 1 行（1 \leq i \leq N）では、ドミノ i の許容衝撃値 P_i と衝撃増分 D_i がスペース区切りで与えられる。
  • 第 N + 2 行から第 N + 1 + Q 行では、各実験の初期衝撃値が与えられる。
  • 第 N + 1 + j 行（1 \leq j \leq Q）では、j 番目の実験における初期衝撃値 S_j が与えられる。

出力

Q 行出力せよ。第 j 行（1 \leq j \leq Q）には、j 番目の実験において正常に倒れた最後のドミノの番号を出力せよ。すべてのドミノが正常に倒れた場合は N を出力せよ。正常に倒れたドミノが 1 つもなかった場合は 0 を出力せよ。

入力例 1

3 3
5 2
6 3
20 0
3
5
6

出力例 1

3
1
0

入力例 2

4 4
2 0
2 0
2 0
2 0
0
1
2
3

出力例 2

4
4
4
0

入力例 3

10 6
8 5
20 0
18 4
30 10
60 0
25 2
26 8
40 1
42 3
100 0
0
5
6
8
15
1

出力例 3

10
10
6
5
0
10

入力例 4

40 20
200000000 30000000
250000000 30000000
300000000 30000000
350000000 30000000
400000000 30000000
450000000 30000000
500000000 30000000
550000000 30000000
600000000 30000000
650000000 30000000
680000000 100000000
760000000 100000000
840000000 100000000
920000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 0
900000000 50000000
850000000 50000000
800000000 50000000
750000000 50000000
700000000 50000000
650000000 50000000
600000000 50000000
550000000 50000000
500000000 50000000
450000000 50000000
400000000 50000000
350000000 50000000
300000000 50000000
250000000 50000000
200000000 50000000
150000000 0
120000000 0
100000000 0
80000000 0
60000000 0
0
10000000
50000000
90000000
120000000
150000000
180000000
200000000
220000000
240000000
260000000
280000000
300000000
350000000
400000000
450000000
500000000
600000000
800000000
1000000000

出力例 4

18
17
17
17
16
16
16
16
0
0
0
0
0
0
0
0
0
0
0
0

入力例 5

1 5
7 1000000000
0
7
8
1000000000
6

出力例 5

1
1
0
0
1

Score : 366 pts

Problem Statement

Takahashi has built a domino toppling course with N dominoes arranged in a line. The dominoes are numbered from 1 to N from left to right.

Each domino i (1 \leq i \leq N) has a "tolerance value" P_i and an "impact increment" D_i. The tolerance value is the maximum impact value at which the domino can fall normally without being shattered.

In this course, the domino toppling begins by hitting a ball against domino 1. Let S be the initial impact value when the ball hits. The domino toppling proceeds sequentially from domino 1 as follows.

Let C_i denote the impact value when it reaches domino i. For domino 1, C_1 = S.

  • If C_i \leq P_i (the impact value is at most the tolerance value), domino i falls normally. When i < N, the fallen domino i transmits the impact to the next domino i+1, and the impact value reaching domino i+1 is C_{i+1} = C_i + D_i.
  • If C_i > P_i (the impact value exceeds the tolerance value), domino i cannot withstand the impact and is shattered. A shattered domino crumbles without falling, so no impact is transmitted to the next domino, and the domino toppling ends there. A shattered domino is not considered to have "fallen normally."

Takahashi performs Q experiments. Each experiment is independent of the others, and all dominoes are reset to their initial configuration before each experiment. In each experiment j (1 \leq j \leq Q), the initial impact value S_j of the ball hitting domino 1 is given.

For each experiment, determine the number of the last domino that fell normally. If all dominoes fell normally, output N. If even domino 1 did not fall normally (i.e., S_j > P_1), output 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq D_i \leq 10^9 (1 \leq i \leq N)
  • 0 \leq S_j \leq 10^9 (1 \leq j \leq Q)
  • All input values are integers.

Note

The impact value may exceed 10^9 during the domino toppling process. When all dominoes fall normally, the impact value can reach up to S_j + D_1 + D_2 + \cdots + D_{N-1}, but this fits within the range of a 64-bit signed integer.

D_N is given as input, but since there is no domino after domino N, it is not used.

Input

N Q
P_1 D_1
P_2 D_2
\vdots
P_N D_N
S_1
S_2
\vdots
S_Q
  • The first line contains an integer N representing the number of dominoes and an integer Q representing the number of experiments, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the tolerance value and impact increment of each domino are given.
  • The (i + 1)-th line (1 \leq i \leq N) contains the tolerance value P_i and impact increment D_i of domino i, separated by a space.
  • From the (N + 2)-th line to the (N + 1 + Q)-th line, the initial impact value for each experiment is given.
  • The (N + 1 + j)-th line (1 \leq j \leq Q) contains the initial impact value S_j for the j-th experiment.

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain the number of the last domino that fell normally in the j-th experiment. If all dominoes fell normally, output N. If no domino fell normally, output 0.

Sample Input 1

3 3
5 2
6 3
20 0
3
5
6

Sample Output 1

3
1
0

Sample Input 2

4 4
2 0
2 0
2 0
2 0
0
1
2
3

Sample Output 2

4
4
4
0

Sample Input 3

10 6
8 5
20 0
18 4
30 10
60 0
25 2
26 8
40 1
42 3
100 0
0
5
6
8
15
1

Sample Output 3

10
10
6
5
0
10

Sample Input 4

40 20
200000000 30000000
250000000 30000000
300000000 30000000
350000000 30000000
400000000 30000000
450000000 30000000
500000000 30000000
550000000 30000000
600000000 30000000
650000000 30000000
680000000 100000000
760000000 100000000
840000000 100000000
920000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 100000000
1000000000 0
900000000 50000000
850000000 50000000
800000000 50000000
750000000 50000000
700000000 50000000
650000000 50000000
600000000 50000000
550000000 50000000
500000000 50000000
450000000 50000000
400000000 50000000
350000000 50000000
300000000 50000000
250000000 50000000
200000000 50000000
150000000 0
120000000 0
100000000 0
80000000 0
60000000 0
0
10000000
50000000
90000000
120000000
150000000
180000000
200000000
220000000
240000000
260000000
280000000
300000000
350000000
400000000
450000000
500000000
600000000
800000000
1000000000

Sample Output 4

18
17
17
17
16
16
16
16
0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 5

1 5
7 1000000000
0
7
8
1000000000
6

Sample Output 5

1
1
0
0
1