以下のような dp を考えます。

\(dp_i[k] = \) \(i\) 日目以降に \(k\) 人目 を脱出させるために必要なメダルの数

これは \(k\) について単調増加に管理します。

これを \(i\) の降順に更新していくことを考えましょう。

---

\(B_i, C_i\) の処理をします。

\(i\) 日目を考えると

• 今日脱出させるには \(B_i + C_i\)
• 未来で脱出させるには \(B_i + dp_{i+1}[k]\)

枚のメダルが必要です。 よって

• \(dp_{i+1}[k] > C_i\) ならば \(C_i\) にする
• すべてに \(B_i\) を足す

をすればよいです。

---

次に \(A_i\) を処理します。

このとき「脱出コストが小さい人」がより有利になるようにして損しません。（次の人を脱出させる前にその人を脱出させるため、また \(B_i, C_i\) による更新によっても損をしないため）

ということで \(k = 1, 2, \dots\) について \(A_i \gt 0\) の間以下の処理をします

• \(d = \min(A_i,dp_i[k])\) として \(A_i\) と \(dp_i[k]\) から \(d\) を引く

最終的に \(dp_1[k] = 0\) である \(k\) の個数が答えです。

---

dp 配列を陽にもつと、とても長い配列が必要になりますが、RLE して同じ値の \(dp[k]\) をまとめて管理すればよいです。

すると（末尾・先頭）の（追加・削除）や全体加算のみで十分です。 deque などで \(O(N)\) です。

---

実装例

（ \(B_i\) や \(C_i\) が非零であることを用いている部分があります。非自明に感じるかもしれません）

from collections import deque

inf = 2 ** 60

def solve():
    n = int(input())
    abc = []
    for i in range(n):
        a, b, c = map(int, input().split())
        abc.append((a, b, c))
    
    off = 0
    dq = deque()
    dq.append([0, 0])
    dq.append([inf, inf])

    for a, b, c in reversed(abc):
        while dq[-1][0] + off >= c:
            dq.pop()
        
        dq.append([c - off, inf])
        
        off += b
        z = 0
        while a and dq:
            k2, v = dq[0]
            k = k2 + off
                
            if a >= k * v:
                a -= k * v
                z += v
                dq.popleft()
            else:
                q, r = divmod(a, k)
                dq[0][1] -= (q + 1) if r else q 
                z += q
                if dq[0][1] == 0:
                    dq.popleft()
                if r:
                    dq.appendleft([k-r-off, 1])                    
                break
        
        dq.appendleft([-off, z])
    
    print(dq[0][1])

t = int(input())
for i in range(t):
    solve()