Overview

This is a problem where we harvest a total of at most \(M\) times from \(N\) types of fruit trees, maximizing the total number of fruits obtained. Since each tree yields less fruit with each successive harvest, the optimal strategy is to greedily harvest from “the tree that yields the most fruit” each time.

Analysis

Key Insight: Greedy is Optimal

Each harvest can be considered independently as “which tree yields the most fruit at this moment?” This is because the number of fruits obtained from the \(k\)-th harvest of tree \(i\) is determined as \(\max(F_i - (k-1) \times D_i, \ 0)\), and changing the order of harvests does not change the sequence of yields from each tree.

For example, if tree A’s harvest yields are \([10, 7, 4, 1]\) and tree B’s harvest yields are \([8, 3]\), then for a total of \(M = 3\) harvests, the optimal choice is to pick the top 3 values \(10, 8, 7\) from all candidates \(\{10, 8, 7, 4, 3, 1\}\) in descending order.

Problem with the Naive Approach

The method of enumerating and sorting all harvest candidates from all trees is infeasible in both memory and time, since the number of possible harvests per tree can be extremely large (\(F_i / D_i\) can be up to \(10^9\)).

Solution: Priority Queue (Heap)

Instead of enumerating all candidates, we manage only the “yield of the next harvest” for each tree using a heap. After extracting the maximum value, we push the next harvest yield for that tree back into the heap, repeating this operation at most \(M\) times. This allows us to efficiently process only what is needed.

Algorithm

1. Initialization: For each tree \(i\), if the first harvest yield \(F_i > 0\), insert \(F_i\) into a max-heap (in Python, since the heap is a min-heap, insert \(-F_i\)).
2. Greedily harvest \(M\) times:
   • Extract the maximum value \(v\) from the heap.
   • If \(v \leq 0\), there is no benefit in harvesting further, so stop.
   • Add \(v\) to the total.
   • If the next harvest yield \(v - D_i\) is positive, push it back into the heap.
3. Output the total.

Concrete Example

For \(N=2, M=3\), tree 1: \((F_1, D_1) = (10, 3)\), tree 2: \((F_2, D_2) = (8, 5)\):

Harvest #	Heap State	Selected	Next Value
1st	\(\{10, 8\}\)	10 (tree 1)	\(10 - 3 = 7\)
2nd	\(\{8, 7\}\)	8 (tree 2)	\(8 - 5 = 3\)
3rd	\(\{7, 3\}\)	7 (tree 1)	\(7 - 3 = 4\)

Total: \(10 + 8 + 7 = 25\)

Complexity

• Time Complexity: \(O((N + M) \log N)\)
  • \(O(N \log N)\) for initial heap construction, \(O(M \log N)\) for at most \(M\) heap operations.
• Space Complexity: \(O(N)\)
  • The heap contains at most \(N\) entries, one “next harvest yield” per tree.

Implementation Notes

• Python’s heap is a min-heap, so we store negated values to use it as a max-heap.

• Trees whose harvest yield drops to \(0\) or below are not pushed back into the heap, avoiding unnecessary operations.

• If the heap becomes empty (all trees’ harvest yields have reached \(0\)), the loop terminates even before reaching \(M\) iterations.

• Input is read all at once using sys.stdin.buffer.read() to ensure speed when handling large inputs.

  Source Code

import heapq

def solve():
    import sys
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    # Use a max-heap (negate values for Python's min-heap)
    # Each entry: (-current_yield, F_i, D_i, k) where k is the next harvest number (1-indexed)
    # yield for k-th harvest = max(F_i - (k-1)*D_i, 0)
    
    heap = []
    for i in range(N):
        F = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        if F > 0:
            heapq.heappush(heap, (-F, F, D))
    
    total = 0
    for _ in range(M):
        if not heap:
            break
        neg_val, F, D = heapq.heappop(heap)
        val = -neg_val
        if val <= 0:
            break
        total += val
        # Next harvest from this tree: val - D
        next_val = val - D
        if next_val > 0:
            heapq.heappush(heap, (-next_val, F, D))
    
    print(total)

solve()

---

This editorial was generated by claude4.6opus-thinking.