\(d_i=A_i-B_i-C_i\) とします。 この問題は、各 \(j\) について、 \(S_j+\sum_{i=0}^{K}d_{((L_j-1+i) \bmod N) +1)}\) が \(0\) 未満となる最小の \(K\) を(存在する場合は)求める問題です。

ここで、\(d_i\) の加算は \(N\) 日周期です。\(1\) 周期後は、\(S_j\) から \(S_j+\sum_{i=1}^{N}d_i\) になっています。\(T=\sum_{i=1}^{N}d_i\) の値の正負によって場合分けをします。

\(T \geq 0\) の場合

最初の周期で倒産しない限り、倒産しません。なので、\(K\) の範囲は \(0\) から \(N-1\) です。

実際に条件を満たす最小の \(K\) はSegment Treeの二分探索などを用いることで計算できます。Segment Treeの各ノードではその区間の左からの累積和の最小値と全体の総和を持つことで二分探索できる形に落とし込めます。

\(T <0\) の場合

\(1\) 周期の間の累積和の最小値を \(m\) とします。 この時、\(S_j+x \times T+ m <0\) を満たす最小の非負整数 \(x\) について \((x+1)\) 周期目の途中に破産します。 \(x\) 周期分を実行した後、\(T \geqq 0\) の場合と同様にSegment Tree上の二分探索で求められます。

よって、時間計算量 \(\mathrm{O}(N+Q\log N)\) で解くことができます。

実装のテクニックとして、これは円環の構造をなしているので　SegmentTreeの長さを \(2N\) にすると実装しやすいです。

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
struct S {
    long long mi, sum;
    S() : mi(0), sum(0) {}
    S(long long v) : mi(v), sum(v) {}
    S(long long a, long long b) : mi(a), sum(b) {}
};
S op(S a, S b) {
    return S(min(a.mi, a.sum + b.mi), a.sum + b.sum);
}
S e() { return S(); }
long long floor_div(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b != 0);
}
int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> d(n);
    for (int i = 0; i < n; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        d[i] = a - b - c;
    }
    atcoder::segtree<S, op, e> seg([&]() {
        vector<S> v(2 * n);
        for (int i = 0; i < n; ++i) v[i] = S(d[i]);
        for (int i = n; i < 2 * n; ++i) v[i] = S(d[i - n]);
        return v;
    }());
    for (int i = 0; i < q; ++i) {
        int l;
        long long s;
        cin >> l >> s;
        l--;
        S ap = seg.prod(l, l + n);
        if (ap.sum >= 0) {
            if (s + ap.mi < 0) {
                auto r = seg.max_right(l, [&](S res) { return res.mi >= -s; });
                cout << r - l + 1 << endl;
                continue;
            } else {
                cout << 0 << endl;
                continue;
            }
        } else {
            long long k = max(0LL, floor_div(s + ap.mi, -ap.sum) + 1);
            long long ans = k * n;
            auto r = seg.max_right(l, [&](S res) { return res.mi >= -(s + ap.sum * k); });
            cout << ans + r - l + 1 << endl;
        }
    }
}