Overview

Each day’s harvest is determined by “which orchard’s how-many-th operation it is,” so the problem can be rephrased as selecting the top \(K\) values from the multiset of “per-operation harvest amounts” across all orchards.
Since constructing this multiset directly would be enormous, we use binary search with a function that counts the number of events exceeding a threshold.

Analysis

For orchard \(i\) (initial \(A_i\) fruits, daily limit \(B_i\)), the sequence of harvest amounts has the following form:

• The first \(d_i-1\) times: \(B_i\) fruits each time
• The last time: \(r_i\) fruits (\(1 \le r_i \le B_i\))
• After that: \(0\)

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

In other words, the “positive harvest amounts” obtainable from orchard \(i\) are
[ \underbrace{B_i,\dots,Bi}{d_i-1\text{ times}},\ r_i ] for a total of \(d_i\) values.
Combining all orchards, the problem becomes selecting the top \(K\) values from a large collection of values.

---

A naive approach of “picking the orchard with the maximum yield each day” using a priority queue is infeasible since \(K\) can be up to \(10^{18}\).
Enumerating and sorting all harvest events is also infeasible since the number of events can be extremely large.

Instead, we use the following idea:

• Fix a value \(p\) and count how many events have harvest amount greater than \(p\)
• This count decreases as \(p\) increases (monotonicity)
• Therefore, we can apply binary search

For orchard \(i\):

• If \(B_i > p\), then all \((d_i-1)\) events with value \(B_i\) are counted
• If \(r_i > p\), the last event is also counted

This allows us to compute: - Count cnt(>p) - Sum sum(>p) in \(O(N)\) time.

Using binary search, we find the smallest \(p\) satisfying
[ \text{cnt}(>p)\le K ] At this point, “take all events with value \(>p\),” and fill the remaining slots with events that have exactly value \(p\):

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

This gives exactly the sum of the top \(K\) values.

Algorithm

1. For each orchard, precompute \(d_i=\lceil A_i/B_i\rceil\) and \(r_i=A_i-(d_i-1)B_i\).
2. Create a function count_sum_gt(p):
   • Iterate over all orchards and return the count cnt and sum s of events with harvest amount \(>p\).
3. Binary search over \(p\in[-1,10^9]\) to find the smallest \(p\) such that cnt(>p) <= K.
4. Recompute cnt_gt, sum_gt = count_sum_gt(p), and output [ \text{ans}=sum_gt+(K-cnt_gt)\cdot p ]
5. As a safeguard, clip the result to the total number of fruits sum(A_i) (theoretically it should never exceed this).

Complexity

• Time complexity: \(O(N \log 10^9)\) (about 30 iterations of binary search × \(O(N)\) per iteration)
• Space complexity: \(O(N)\)

Implementation Notes

• Since \(K\) can be very large, do not simulate day by day.

• It is important that count_sum_gt(p) counts using “\(> p\)” (this makes the correspondence with the final formula straightforward).

• In Python there is no concern about integer overflow, but in other languages 64-bit integers are required.

• Binary search boundaries of lo=-1, hi=1e9 are safe (harvest amounts range from 0 to \(10^9\)).

  Source Code

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()

---

This editorial was generated by gpt-5.3-codex.