概要

各果樹園での収穫を「1日ごとに得られる収穫量の列」に分解すると、各果樹園は \(B_i\) が何回か続き、最後に余りが 1 回だけ現れる形になります。
したがって、全果樹園から得られる「正の収穫量」をまとめて考え、その中から大きいものを \(K\) 個選べば最適です。

考察

この問題で大事なのは、1つの果樹園を何回収穫したとき、各日に何個取れるかを先に整理することです。

果樹園 \(i\) の果物の数が \(A_i\)、1日で最大 \(B_i\) 個取れるとします。
\(A_i\) を \(B_i\) で割ると

• \(q_i = \left\lfloor \dfrac{A_i}{B_i} \right\rfloor\)
• \(r_i = A_i \bmod B_i\)

となります。

すると、この果樹園から各日に得られる収穫量は

• \(B_i\) が \(q_i\) 回
• \(r_i > 0\) なら最後に \(r_i\) が 1 回

です。

例えば \(A_i = 10, B_i = 3\) なら、収穫量の列は

\(3, 3, 3, 1\)

になります。

---

なぜこれでよいのか

各果樹園について、収穫量は

• 最初の何日かは毎回 \(B_i\)
• 最後だけ \(B_i\) 未満の余り
• それ以降は \(0\)

という形です。

つまり、各果樹園は「正の値がいくつか並んだ列」とみなせます。
最終的にやりたいことは、全体でちょうど \(K\) 日選んで合計を最大化することです。

ここで重要なのは、各果樹園の列が 大きい値から小さい値へ並んでいる ことです。
特に余り \(r_i\) は \(r_i < B_i\) なので、もし余りを使うなら、その前にある \(B_i\) たちは必ずそれ以上に価値があります。

したがって、全果樹園の「正の収穫量」を全部集めて、大きいものから \(K\) 個取る だけで最適になります。

---

素朴な方法がなぜ厳しいか

素朴に考えると、

• 毎日、今もっとも多く取れる果樹園を選ぶ
• 収穫後にその果樹園の残量を更新する

というシミュレーションをしたくなります。

しかし \(K \le 10^{18}\) なので、1日ずつ処理するのは不可能です。

また、各果樹園の収穫量列をそのまま全部展開する方法もだめです。
例えば \(A_i = 10^9, B_i = 1\) だと、その果樹園だけで \(10^9\) 回分あります。

---

どう解決するか

各果樹園 \(i\) について

• 値 \(B_i\) が \(q_i\) 個
• 値 \(r_i\) が 1 個（\(r_i > 0\) のとき）

ある、とだけ数えれば十分です。

つまり、実際に列を展開する代わりに

• 「値 \(v\) が何個あるか」

を辞書で管理します。

その後、値を大きい順に見ていき、

• その値を何個使えるか
• 残り何日あるか

を確認しながら、貪欲に答えへ加算すればよいです。

アルゴリズム

1. 各果樹園について \(A_i, B_i\) を読む。
2. \(q_i, r_i = \mathrm{divmod}(A_i, B_i)\) を求める。
3. 辞書 cnt に対して
   • cnt[B_i] += q_i
   • r_i > 0 なら cnt[r_i] += 1 を行う。
4. cnt のキー（収穫量）を大きい順に走査する。
5. 各値 \(v\) について、
   • その値を使える個数は cnt[v]
   • 残り日数を \(K\) として、take = min(K, cnt[v])
   • 答えに take * v を加える
   • \(K\) を take だけ減らす
6. \(K=0\) になったら終了。
7. もし正の収穫量を全部使い切っても \(K\) が余っていれば、残りは \(0\) を収穫するだけなので無視してよい。

例

例えば

• \((A,B)=(10,3)\) から \(3,3,3,1\)
• \((A,B)=(8,5)\) から \(5,3\)

が得られます。

全体の正の収穫量は

\(5,3,3,3,3,1\)

です。
\(K=4\) なら大きい順に 4 個選んで

\(5+3+3+3=14\)

が最大です。

計算量

• 時間計算量: \(O(N + M \log M)\)（\(M\) は異なる収穫量の種類数、\(M \le 2N\) なので全体で \(O(N \log N)\)）
• 空間計算量: \(O(M)\)（最大でも \(O(N)\)）

実装のポイント

• 各果樹園を実際に何日もシミュレーションしないことが重要です。

• divmod(A, B) を使うと、商と余りを同時に求められて簡潔です。

• q_i は非常に大きくなる可能性があるので、列として展開せず「個数」として管理します。

• \(K\) や答えは大きくなるので、take * v の計算でオーバーフローしない型が必要ですが、Python なら問題ありません。

  ソースコード

import sys
from collections import defaultdict

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N, K = data[0], data[1]
    cnt = defaultdict(int)

    idx = 2
    for _ in range(N):
        A = data[idx]
        B = data[idx + 1]
        idx += 2

        q, r = divmod(A, B)
        if q:
            cnt[B] += q
        if r:
            cnt[r] += 1

    ans = 0
    for v in sorted(cnt.keys(), reverse=True):
        if K == 0:
            break
        take = min(K, cnt[v])
        ans += take * v
        K -= take

    print(ans)

if __name__ == "__main__":
    main()

---

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