E - Company Management Simulation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は N 日間を 1 サイクルとする経営計画を立てました。この計画では、各日ごとに売上、仕入れ費用、人件費が決まっています。

経営計画の i 日目 (1 \leq i \leq N) では、その日の終了時に資金が A_i - B_i - C_i 円だけ増加します。ここで A_i は売上、B_i は仕入れ費用、C_i は人件費を表します。（増加量が負の場合、資金は減少します。）

この経営計画は N 日目の翌日に再び 1 日目に戻り、同じ計画を無限に繰り返します。

ある日の終了時点で資金が 0 円未満（負）になった場合、会社は倒産したとみなします。

Q 個の質問が与えられます。j 番目の質問では、高橋君が経営計画の L_j 日目から経営を始め、L_j 日目の処理が行われる前の時点での資金が S_j 円であるとします。

その後、経営計画の順に従って毎日経営を行います。すなわち、経営計画上の日は L_j, L_j+1, \ldots, N, 1, 2, \ldots の順に進みます。経営を行った最初の日（経営計画の L_j 日目）を「経営開始から 1 日目」と数えます。

各質問について、経営開始から何日目の終了時点で初めて倒産するかを出力してください。無限に経営を続けても倒産しない場合は 0 を出力してください。

制約

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 0 \leq C_i \leq 10^9
  • 1 \leq L_j \leq N
  • 0 \leq S_j \leq 10^{12}
  • 入力はすべて整数である

入力

N Q
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N
L_1 S_1
L_2 S_2
\vdots
L_Q S_Q
  • 1 行目には、経営計画のサイクル日数を表す整数 N と、質問の個数を表す整数 Q が、スペース区切りで与えられる。
  • 続く N 行では、経営計画の各日の情報が与えられる。
  • 1 + i 行目 (1 \leq i \leq N) では、i 日目の売上を表す A_i、仕入れ費用を表す B_i、人件費を表す C_i が、スペース区切りで与えられる。
  • 続く Q 行では、各質問の情報が与えられる。
  • 1 + N + j 行目 (1 \leq j \leq Q) では、j 番目の質問における経営開始日を表す L_j と、初期資金を表す S_j が、スペース区切りで与えられる。

出力

Q 行出力してください。

j 行目には、j 番目の質問について、初めて倒産するのが経営開始から何日目の終了時点であるかを整数で出力してください。倒産しない場合は 0 を出力してください。

入力例 1

3 5
10 3 2
4 7 5
8 4 3
1 0
1 10
2 7
3 1
2 20

出力例 1

2
14
1
3
22

入力例 2

4 4
5 2 3
10 4 1
0 0 0
7 3 2
1 0
2 1
3 100
4 5

出力例 2

0
0
0
0

入力例 3

8 8
100 30 20
20 50 10
0 40 30
80 20 20
10 5 5
50 60 20
200 100 50
30 20 40
1 0
2 25
3 100
4 10
5 60
6 5
7 1000
8 15

出力例 3

3
1
17
8
7
1
269
1

入力例 4

20 15
1000000000 400000000 300000000
200000000 500000000 100000000
0 600000000 500000000
750000000 250000000 250000000
123456789 123456789 0
900000000 100000000 100000000
10000000 20000000 30000000
500000000 600000000 100000000
1000000000 0 0
0 0 0
300000000 100000000 250000000
800000000 900000000 50000000
450000000 200000000 100000000
100000000 300000000 400000000
600000000 100000000 100000000
700000000 350000000 350000000
1 1000000000 0
999999999 1 1
250000000 250000000 250000000
400000000 100000000 200000000
1 0
1 1000000000000
3 500000000
5 123456789
7 10000000
9 0
10 100
12 800000000
14 1500000000
16 0
18 999999999999
20 300000000
4 700000000
11 250000000
15 50

出力例 4

2
0
1
19
1
9
2
6
10
2
0
4
0
4
3

入力例 5

1 5
0 1000000000 1000000000
1 0
1 1
1 1999999999
1 2000000000
1 1000000000000

出力例 5

1
1
1
2
501

Score : 433 pts

Problem Statement

Takahashi has created a management plan that cycles every N days. In this plan, the revenue, purchasing costs, and labor costs are determined for each day.

On day i (1 \leq i \leq N) of the management plan, at the end of that day, the funds increase by A_i - B_i - C_i yen, where A_i represents revenue, B_i represents purchasing costs, and C_i represents labor costs. (If the increase is negative, the funds decrease.)

This management plan returns to day 1 on the day after day N, and the same plan repeats infinitely.

If at the end of any day the funds become less than 0 yen (negative), the company is considered to have gone bankrupt.

Q queries are given. In the j-th query, Takahashi starts management from day L_j of the management plan, and his funds are S_j yen at the point before day L_j's processing occurs.

After that, management is conducted daily following the order of the management plan. That is, the days in the management plan proceed in the order L_j, L_j+1, \ldots, N, 1, 2, \ldots. The first day on which management is conducted (day L_j of the management plan) is counted as "day 1 since the start of management."

For each query, output on which day since the start of management the company goes bankrupt for the first time (at the end of that day). If the company never goes bankrupt no matter how long management continues, output 0.

Constraints

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 0 \leq B_i \leq 10^9
  • 0 \leq C_i \leq 10^9
  • 1 \leq L_j \leq N
  • 0 \leq S_j \leq 10^{12}
  • All inputs are integers

Input

N Q
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N
L_1 S_1
L_2 S_2
\vdots
L_Q S_Q
  • The first line contains an integer N representing the number of days in the management plan cycle and an integer Q representing the number of queries, separated by a space.
  • The following N lines give information about each day of the management plan.
  • The (1 + i)-th line (1 \leq i \leq N) contains A_i representing the revenue on day i, B_i representing the purchasing costs, and C_i representing the labor costs, separated by spaces.
  • The following Q lines give information about each query.
  • The (1 + N + j)-th line (1 \leq j \leq Q) contains L_j representing the starting day of management for the j-th query and S_j representing the initial funds, separated by a space.

Output

Output Q lines.

On the j-th line, output an integer representing on which day since the start of management the company first goes bankrupt (at the end of that day) for the j-th query. If the company does not go bankrupt, output 0.

Sample Input 1

3 5
10 3 2
4 7 5
8 4 3
1 0
1 10
2 7
3 1
2 20

Sample Output 1

2
14
1
3
22

Sample Input 2

4 4
5 2 3
10 4 1
0 0 0
7 3 2
1 0
2 1
3 100
4 5

Sample Output 2

0
0
0
0

Sample Input 3

8 8
100 30 20
20 50 10
0 40 30
80 20 20
10 5 5
50 60 20
200 100 50
30 20 40
1 0
2 25
3 100
4 10
5 60
6 5
7 1000
8 15

Sample Output 3

3
1
17
8
7
1
269
1

Sample Input 4

20 15
1000000000 400000000 300000000
200000000 500000000 100000000
0 600000000 500000000
750000000 250000000 250000000
123456789 123456789 0
900000000 100000000 100000000
10000000 20000000 30000000
500000000 600000000 100000000
1000000000 0 0
0 0 0
300000000 100000000 250000000
800000000 900000000 50000000
450000000 200000000 100000000
100000000 300000000 400000000
600000000 100000000 100000000
700000000 350000000 350000000
1 1000000000 0
999999999 1 1
250000000 250000000 250000000
400000000 100000000 200000000
1 0
1 1000000000000
3 500000000
5 123456789
7 10000000
9 0
10 100
12 800000000
14 1500000000
16 0
18 999999999999
20 300000000
4 700000000
11 250000000
15 50

Sample Output 4

2
0
1
19
1
9
2
6
10
2
0
4
0
4
3

Sample Input 5

1 5
0 1000000000 1000000000
1 0
1 1
1 1999999999
1 2000000000
1 1000000000000

Sample Output 5

1
1
1
2
501