概要

各日の収穫は「どの果樹園の何回目の作業か」で収穫量が決まるので、問題は全果樹園の“1回ごとの収穫量”を並べた多重集合から、大きい順に \(K\) 個選ぶ問題に言い換えられます。
これを直接作ると巨大になるため、しきい値に対する個数を数える関数を使って二分探索します。

考察

果樹園 \(i\)（初期 \(A_i\) 個、1日上限 \(B_i\) 個）について、収穫量の列は次の形です。

• 最初の \(d_i-1\) 回は毎回 \(B_i\) 個
• 最後の1回は \(r_i\) 個（\(1 \le r_i \le B_i\)）
• それ以降は \(0\)

ここで [ d_i=\left\lceil \frac{A_i}{B_i}\right\rceil,\quad r_i=A_i-(d_i-1)B_i ] です。

つまり果樹園 \(i\) から得られる「正の収穫量」は
[ \underbrace{B_i,\dots,Bi}{d_i-1\text{ 回}},\ r_i ] の合計 \(d_i\) 個です。
全果樹園分をまとめると「たくさんの値」から上位 \(K\) 個を取る問題になります。

---

素朴に「毎日最大の果樹園を選ぶ」を優先度キューでやると、\(K\) が最大 \(10^{18}\) のため不可能です。
また全ての収穫イベントを列挙してソートするのも、イベント数が最大で非常に大きくなり不可能です。

そこで次の発想を使います。

• ある値 \(p\) を固定して、「収穫量が \(p\) より大きいイベント」が何個あるかを数える
• その個数は \(p\) が大きいほど減る（単調性）
• よって二分探索できる

果樹園 \(i\) に対して：

• \(B_i > p\) なら、\(B_i\) のイベントが \((d_i-1)\) 個すべてカウントされる
• \(r_i > p\) なら、最後の1個もカウントされる

これで - 個数 cnt(>p) - それらの合計 sum(>p) を \(O(N)\) で計算できます。

二分探索で
[ \text{cnt}(>p)\le K ] を満たす最小の \(p\) を求めます。
このとき「\(>p\) のものは全部取る」とまだ足りない分は、ちょうど値 \(p\) のイベントから埋めればよいので

[ \text{答え}=\text{sum}(>p)+(K-\text{cnt}(>p))\cdot p ]

となります（上位 \(K\) 個の和そのもの）。

アルゴリズム

1. 各果樹園について \(d_i=\lceil A_i/B_i\rceil\) と \(r_i=A_i-(d_i-1)B_i\) を前計算。
2. 関数 count_sum_gt(p) を作る：
   • 全果樹園を見て、収穫量 \(>p\) のイベント数 cnt と合計 s を返す。
3. \(p\in[-1,10^9]\) で二分探索し、cnt(>p) <= K を満たす最小の \(p\) を求める。
4. cnt_gt, sum_gt = count_sum_gt(p) を再計算し、 [ \text{ans}=sum_gt+(K-cnt_gt)\cdot p ] を出力する。
5. 念のため総果実数 sum(A_i) を上限にクリップ（理論上超えない）。

計算量

• 時間計算量: \(O(N \log 10^9)\)（二分探索約30回 × 各回 \(O(N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• \(K\) が非常に大きいので、1日ずつシミュレーションしない。

• count_sum_gt(p) は 「> p」 で数えるのが重要（最終式と対応が取りやすい）。

• Python では整数オーバーフローの心配はないが、他言語なら 64bit 整数必須。

• 二分探索の境界は lo=-1, hi=1e9 で安全（収穫量は 0〜\(10^9\)）。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]

    if K == 0:
        print(0)
        return

    total_fruits = sum(a for a, _ in AB)

    # 各果樹園 i について:
    # d_i = ceil(A_i / B_i) 日で空になる
    # t 日目(1-indexed)の収穫量は:
    #   t < d_i : B_i
    #   t = d_i : rem_i (= A_i - (d_i-1)*B_i, 1..B_i)
    #   t > d_i : 0
    d = []
    rem = []
    for a, b in AB:
        di = (a + b - 1) // b
        d.append(di)
        rem.append(a - (di - 1) * b)

    # ある閾値 p に対し、"収穫量 > p" の回数と合計値を計算
    # 回数:
    #   B_i > p のとき、通常日の回数 (d_i-1)
    #   rem_i > p のとき、最終日1回
    # 合計:
    #   (d_i-1)*B_i + (rem_i if rem_i > p else 0)
    def count_sum_gt(p: int):
        cnt = 0
        s = 0
        for (a, b), di, ri in zip(AB, d, rem):
            if b > p:
                c = di - 1
                if c > 0:
                    cnt += c
                    s += c * b
            if ri > p:
                cnt += 1
                s += ri
        return cnt, s

    # p を二分探索: count(>p) <= K を満たす最小の p
    # p in [-1, 1e9]
    lo, hi = -1, 10**9
    while hi - lo > 1:
        mid = (lo + hi) // 2
        cnt, _ = count_sum_gt(mid)
        if cnt <= K:
            hi = mid
        else:
            lo = mid

    p = hi
    cnt_gt, sum_gt = count_sum_gt(p)

    # ちょうど K 個選ぶため、残りは値 = p のものから選ぶ
    ans = sum_gt + (K - cnt_gt) * p

    # 理論上 ans <= total_fruits だが、念のため
    if ans > total_fruits:
        ans = total_fruits

    print(ans)

if __name__ == "__main__":
    main()

---

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