概要

各木が生み出す「収穫量の列」（等差数列）の中から、全体で高い順に最大 \(M\) 個を選んだときの合計値を求める問題です。直接列を列挙せず、「しきい値以上の個数」を数えて二分探索で解きます。

考察

重要な観察

木 \(i\) の \(k\) 回目の収穫量は
\(\max(F_i-(k-1)D_i,\,0)\)
なので、正の部分だけを見ると

• \(F_i,\, F_i-D_i,\, F_i-2D_i,\,\dots\)

という等差数列になります（途中で \(0\) 以下になったら終了）。

したがって問題は、

全ての木が持つ（正の）収穫量を全部集めた巨大な多重集合から、値が大きいものを上位 \(M\) 個取って合計する

という形に言い換えられます。

素朴解がダメな理由

• 各木から何回収穫するかは最大で \(M\) 回まであり得ます。
• 例えば優先度付きキューで「次に大きい収穫」を \(M\) 回取り出す方法は、操作回数が \(M\) なので \(O(M\log N)\) で一見良さそうですが、今回はより本質的に「全体で上位 \(M\) 個の合計」を高速に求めたいです（また、実装や定数も重くなりがちです）。
• さらに、全収穫量を列挙すると最悪で \(O(NM)\) になり到底間に合いません。

解決方針（しきい値で数える）

「値が \(x\) 以上の収穫量が全部で何個あるか」を数える関数を考えます。

木 \(i\) について、\(x \le F_i\) のとき - \(F_i-(k-1)D_i \ge x\) - \(\Rightarrow (k-1) \le \dfrac{F_i-x}{D_i}\) - よって個数は \(k = \left\lfloor\dfrac{F_i-x}{D_i}\right\rfloor + 1\)

これを全木で足せば、「\(x\) 以上の個数」が \(O(N)\) で求まります。

そして - \(x\) を大きくすると「\(x\) 以上の個数」は単調に減る ので、二分探索で「上位 \(M\) 個の境界となる値（しきい値）」を探せます。

アルゴリズム

1. まず「\(1\) 以上の収穫量の総数」\(total\_pos\) を数える
   
   • \(total\_pos \le M\) なら、正の収穫量は全部取れるので答えは「全ての正の収穫量の総和」。
2. そうでなければ、二分探索で最大の \(x\) を探す：
   • 条件： 「\(x\) 以上の収穫量が \(M\) 個以上存在する」
   • つまり count_ge(x) >= M を満たす最大の \(x\)。
3. 見つけた \(x\) を境界として、答えを次のように構成する：
   • \(x\) より大きい収穫量（\(x+1\) 以上）を全て足す（個数を \(cnt\_gt\)、和を \(sum\_gt\) とする）
   • 残り \(M-cnt\_gt\) 個は、ちょうど値 \(x\) の収穫量で埋めればよい
     （二分探索の定義より、\(x\) 以上は \(M\) 個以上あるので、\(x\) は必要個数だけ必ず存在）
   • よって最終答えは
     \(ans = sum\_gt + (M-cnt\_gt)\times x\)

和の計算（等差数列の和）

木 \(i\) で「\(x\) 以上の項数」が \(k\) 個あるとき、最後の項は
\(last = F_i-(k-1)D_i\)
和は等差数列の和で
\(\dfrac{k(F_i+last)}{2}\)
これを全木で足して count_sum_ge(x) として計算しています。

計算量

• 時間計算量: \(O(N \log(\max F_i))\)
  （二分探索が \(\log(\max F_i)\) 回、各回で \(O(N)\) 集計）
• 空間計算量: \(O(N)\)
  （\(F_i, D_i\) の配列を保持）

実装のポイント

• 境界処理：最終的に「\(x\) より大きい（\(x+1\) 以上）」を先に全部足し、残りを \(x\) で埋めると重複なく数えられます。
• オーバーフロー：Python の int は多倍長なので安全ですが、和は最大で非常に大きくなるため（\(10^9 \times 2\times 10^5\) 規模）、他言語では int64 が必須です。
• 高速入力：\(N\) が \(2\times 10^5\) なので sys.stdin.buffer.read() でまとめて読むと安定して高速です。

ソースコード

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    N, M = it[0], it[1]
    Fs = [0] * N
    Ds = [0] * N
    mx = 0
    idx = 2
    for i in range(N):
        f = it[idx]; d = it[idx + 1]
        idx += 2
        Fs[i] = f
        Ds[i] = d
        if f > mx:
            mx = f

    def count_ge(x: int) -> int:
        tot = 0
        for f, d in zip(Fs, Ds):
            if f >= x:
                tot += (f - x) // d + 1
        return tot

    def count_sum_ge(x: int):
        totc = 0
        tots = 0
        for f, d in zip(Fs, Ds):
            if f >= x:
                k = (f - x) // d + 1
                last = f - (k - 1) * d
                tots += k * (f + last) // 2
                totc += k
        return totc, tots

    total_pos = count_ge(1)
    if total_pos <= M:
        _, s = count_sum_ge(1)
        print(s)
        return

    lo, hi = 1, mx + 1  # find largest x with count_ge(x) >= M
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if count_ge(mid) >= M:
            lo = mid
        else:
            hi = mid

    x = lo
    cnt_gt, sum_gt = count_sum_ge(x + 1)  # terms strictly greater than x
    ans = sum_gt + (M - cnt_gt) * x
    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。