/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 625 点
問題文
10^{100} 人の園児がゲーム会場にいます。はじめはどの園児もメダルを持っていません。
園児は、脱落か脱出のいずれかをした時点で、またその時点に限り、会場を去ります。
ゲームは N 日からなります。i 日目 (1 \leq i \leq N) は以下の一連の処理を順に実行します。
- 会場にいる園児の持っているメダルをすべて回収し、その合計枚数を s とおく。
- s + A_i 枚のメダルを、会場にいる園児のあいだで自由に分配する(会場に園児がいない場合は何もしない)。
- 会場にいる園児のうち、メダル所持数が B_i 枚未満の者は脱落する。メダル所持数が B_i 枚以上の者は、メダルを B_i 枚ずつ失う。
- 会場にいる園児のうち、メダル所持数が C_i 枚以上の者は、各々がこのタイミングで脱出するか会場に残るかを選ぶ。
N 日間が終わった時点で会場に残っている園児は、脱落します。
最終的に脱出する園児の人数としてあり得る最大値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 3 \times 10^5
- 1 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^6
- 1 \leq B_i \leq 10^6
- 1 \leq C_i \leq 10^6
- 全てのテストケースにおける N の総和は 3 \times 10^5 以下
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_{1}
\mathrm{case}_{2}
\vdots
\mathrm{case}_{T}
各テストケースは以下の形式で与えられる。
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
出力
各テストケースに対する答えを順に、改行区切りで出力せよ。
入力例 1
2 4 16 2 3 15 2 4 1 3 5 20 5 5 2 41404 1 941738 211877 205711 417821
出力例 1
5 0
1 番目のテストケースについて考えます。園児たちが以下のように行動することで、脱出人数は 5 人になります。
- 1 日目の開始時点で 10^{100} 人の園児から s = 0 枚のメダルを回収する。その後、以下のように行動する。
- 0 + 16 = 16 枚のメダルを配分し、各園児のメダル所持数を (5,5,2,2,2,0,\dots,0) にする。
- メダルを持っていない 10^{100} - 5 人が脱落し、残りの 5 人のメダル所持数は (3,3,0,0,0) になる。
- メダルを 3 枚持っている園児 2 人が脱出を選び、残りの 3 人のメダル所持数は (0,0,0) になる。
- 2 日目の開始時点で 3 人の園児から s = 0 枚のメダルを回収する。その後、以下のように行動する。
- 0 + 15 = 15 枚のメダルを配分し、各園児のメダル所持数を (6,6,3) にする。
- 誰も脱落せず、残りの 3 人のメダル所持数は (4,4,1) になる。
- メダルを 4 枚持っている園児 1 人が脱出を選び、残りの 2 人のメダル所持数は (4,1) になる。
- 3 日目の開始時点で 2 人の園児から s = 5 枚のメダルを回収する。その後、以下のように行動する。
- 5 + 1 = 6 枚のメダルを配分し、各園児のメダル所持数を (3,3) にする。
- 誰も脱落せず、残りの 2 人のメダル所持数は (0,0) になる。
- 誰も脱出しない。
- 4 日目の開始時点で 2 人の園児から s = 0 枚のメダルを回収する。その後、以下のように行動する。
- 0 + 20 = 20 枚のメダルを配分し、各園児のメダル所持数を (10,10) にする。
- 誰も脱落せず、残りの 2 人のメダル所持数は (5,5) になる。
- メダルを 5 枚持っている園児 2 人が脱出を選び、会場から園児がいなくなる。
2 番目のテストケースにおいて、園児は 1 人も脱出できません。
Score : 625 points
Problem Statement
There are 10^{100} kids at a game venue. Initially, no kid has any medals.
A kid leaves the venue exactly when they either drop out or escape.
The game consists of N days. On day i (1 \leq i \leq N), the following sequence of operations is performed in order.
- Collect all medals held by the kids at the venue, and let s be the total number of collected medals.
- Distribute s + A_i medals freely among the kids at the venue (if there are no kids at the venue, do nothing).
- Among the kids at the venue, those with fewer than B_i medals drop out. Those with at least B_i medals each lose B_i medals.
- Among the kids at the venue, those with at least C_i medals each choose whether to escape at this point or remain at the venue.
Kids who remain at the venue at the end of the N days drop out.
Find the maximum possible number of kids who ultimately escape.
You are given T test cases; solve each of them.
Constraints
- 1 \leq T \leq 3 \times 10^5
- 1 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^6
- 1 \leq B_i \leq 10^6
- 1 \leq C_i \leq 10^6
- The sum of N over all test cases is at most 3 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_{1}
\mathrm{case}_{2}
\vdots
\mathrm{case}_{T}
Each test case is given in the following format:
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 1
2 4 16 2 3 15 2 4 1 3 5 20 5 5 2 41404 1 941738 211877 205711 417821
Sample Output 1
5 0
Consider the first test case. By acting as follows, five kids can escape.
- At the start of day 1, collect s = 0 medals from 10^{100} kids. Then, proceed as follows.
- Distribute 0 + 16 = 16 medals so that the kids' medal counts become (5, 5, 2, 2, 2, 0, \dots, 0).
- The 10^{100} - 5 kids with no medals drop out, and the remaining 5 kids' medal counts become (3, 3, 0, 0, 0).
- The 2 kids with 3 medals each choose to escape, and the remaining 3 kids' medal counts become (0, 0, 0).
- At the start of day 2, collect s = 0 medals from 3 kids. Then, proceed as follows.
- Distribute 0 + 15 = 15 medals so that the kids' medal counts becomes (6, 6, 3).
- No one drops out, and the remaining 3 kids' medal counts become (4, 4, 1).
- 1 kid with 4 medals chooses to escape, and the remaining 2 kids' medal counts become (4, 1).
- At the start of day 3, collect s = 5 medals from 2 kids. Then, proceed as follows.
- Distribute 5 + 1 = 6 medals so that the kids' medal counts becomes (3, 3).
- No one drops out, and the remaining 2 kids' medal counts become (0, 0).
- No one escapes.
- At the start of day 4, collect s = 0 medals from 2 kids. Then, proceed as follows.
- Distribute 0 + 20 = 20 medals so that the kids' medal counts becomes (10, 10).
- No one drops out, and the remaining 2 kids' medal counts become (5, 5).
- The 2 kids with 5 medals each choose to escape, and the venue becomes empty.
In the second test case, not a single kid can escape.