Overview

When we decompose the harvest at each orchard into “a sequence of harvest amounts obtained per day,” each orchard takes the form where \(B_i\) appears several times, followed by a remainder appearing exactly once at the end.
Therefore, we can gather all “positive harvest amounts” from all orchards together and select the \(K\) largest ones for the optimal solution.

Analysis

The key to this problem is first organizing how many fruits are obtained each day when harvesting from a single orchard multiple times.

Let the number of fruits in orchard \(i\) be \(A_i\), and the maximum harvestable per day be \(B_i\).
Dividing \(A_i\) by \(B_i\) gives:

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

Then, the harvest amounts obtained from this orchard each day are:

• \(B_i\) appearing \(q_i\) times
• If \(r_i > 0\), then \(r_i\) appearing 1 time at the end

For example, if \(A_i = 10, B_i = 3\), the sequence of harvest amounts is:

\(3, 3, 3, 1\)

---

Why this works

For each orchard, the harvest amounts are:

• \(B_i\) for the first several days
• A remainder less than \(B_i\) only on the last day
• \(0\) thereafter

In other words, each orchard can be viewed as “a sequence of several positive values.”
What we ultimately want to do is select exactly \(K\) days in total to maximize the sum.

The important point here is that each orchard’s sequence is ordered from larger values to smaller values.
In particular, since the remainder \(r_i\) satisfies \(r_i < B_i\), if we use the remainder, the \(B_i\) values that come before it are always at least as valuable.

Therefore, it is optimal to simply gather all “positive harvest amounts” from all orchards and take the \(K\) largest ones.

---

Why the naive approach is infeasible

A naive approach would be:

• Each day, select the orchard that yields the most
• After harvesting, update the remaining amount of that orchard

and simulate this process.

However, since \(K \le 10^{18}\), processing day by day is impossible.

Also, expanding the full harvest sequence for each orchard doesn’t work either.
For example, if \(A_i = 10^9, B_i = 1\), that single orchard has \(10^9\) entries.

---

How to solve it

For each orchard \(i\), it suffices to just count:

• Value \(B_i\) appears \(q_i\) times
• Value \(r_i\) appears 1 time (when \(r_i > 0\))

Instead of actually expanding the sequence, we manage:

• “How many times does value \(v\) appear”

using a dictionary.

Then, we iterate through values in descending order, checking:

• How many of this value can be used
• How many days remain

and greedily add to the answer.

Algorithm

1. Read \(A_i, B_i\) for each orchard.
2. Compute \(q_i, r_i = \mathrm{divmod}(A_i, B_i)\).
3. For a dictionary cnt:
   • cnt[B_i] += q_i
   • If \(r_i > 0\), then cnt[r_i] += 1
4. Iterate through the keys (harvest amounts) of cnt in descending order.
5. For each value \(v\):
   • The number of times this value can be used is cnt[v]
   • With \(K\) remaining days, take = min(K, cnt[v])
   • Add take * v to the answer
   • Decrease \(K\) by take
6. Stop when \(K = 0\).
7. If all positive harvest amounts are exhausted but \(K\) still remains, the rest would just be harvesting \(0\), so it can be ignored.

Example

For instance:

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

All positive harvest amounts are:

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

If \(K=4\), selecting the 4 largest in descending order gives:

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

which is the maximum.

Complexity

• Time complexity: \(O(N + M \log M)\) (where \(M\) is the number of distinct harvest values; since \(M \le 2N\), the overall complexity is \(O(N \log N)\))
• Space complexity: \(O(M)\) (at most \(O(N)\))

Implementation Notes

• It is crucial not to actually simulate each orchard day by day.

• Using divmod(A, B) conveniently computes the quotient and remainder simultaneously.

• \(q_i\) can become very large, so manage it as a “count” rather than expanding it as a sequence.

• Since \(K\) and the answer can be very large, you need a type that doesn’t overflow when computing take * v, but in Python this is not an issue.

  Source Code

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

---

This editorial was generated by gpt-5.4-high.