Overview

This is a problem of maximizing the total amount of fruit harvested from \(N\) types of fruit trees within a total of at most \(M\) harvests. Since each tree’s yield decreases by \(D_i\) with each harvest, the optimal strategy is to always harvest from “the tree with the highest current yield.”

Analysis

Greedy Selection

To maximize the total harvest, the optimal approach is to list all “per-harvest yields” obtainable from all \(N\) types of trees, and select up to \(M\) of them in decreasing order of value.

Naive Approach and Its Limitations

One could use a priority queue (Heap) to always harvest from the tree with the current maximum yield, update the yield, and push it back into the queue, repeating this operation \(M\) times. However, the time complexity of this method is \(O(M \log N)\). Under the constraints of this problem, \(M\) can be up to \(2 \times 10^5\), so this may not fit within the time limit for languages like Python (and it would also fail if \(M\) were even larger).

Binary Search on the Boundary Value (Threshold)

Consider the strategy: “harvest everything with yield \(X\) or more.” For a given value \(X\), the number of harvests \(k_i\) from tree \(i\) where the yield is at least \(X\) can be computed in \(O(1)\) as follows: - \(F_i - (k_i - 1) \times D_i \geq X\) - \((k_i - 1) \times D_i \leq F_i - X\) - \(k_i \leq \frac{F_i - X}{D_i} + 1\) - Therefore, \(k_i = \max(0, \lfloor \frac{F_i - X}{D_i} \rfloor + 1)\) (when \(F_i \geq X\)).

If \(X\) is large, the total number of harvests decreases; if \(X\) is small, the total increases. Using this monotonicity, we can find “the minimum threshold \(X\) such that the total number of harvests is at most \(M\)” via binary search.

Algorithm

1. Determining \(X\) via Binary Search

   • Binary search for the harvest yield threshold \(X\) in the range \([1, 10^9+7]\).
   • For each \(X\), compute the total \(cnt\) of “number of harvests with yield \(\geq X\)” across all tree types.
   • If \(cnt \leq M\), then \(X\) satisfies the condition, so we search for an even smaller \(X\).

2. Computing the Total Harvest

   • Using the determined \(X\), sum up all harvests from each tree where the yield is \(\geq X\).
   • When harvesting \(k_i\) times from tree \(i\), the total is the sum of an arithmetic sequence with first term \(F_i\), common difference \(-D_i\), and \(k_i\) terms:
     • \(Sum_i = \frac{k_i}{2} \times \{2F_i - (k_i - 1)D_i\}\)

3. Handling the Remainder

   • Even after summing all harvests with yield \(\geq X\), the total number of harvests may be less than \(M\).
   • In this case, for the remaining harvests, we can obtain fruit with yield \(X-1\) each (only if \(X-1 > 0\)).

Complexity

• Time Complexity: \(O(N \log (\max F_i))\)
  • The number of binary search iterations is \(\log(10^9) \approx 30\).
  • Each iteration scans all \(N\) tree types, giving an overall complexity of \(O(N \log (\max F_i))\).
• **Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the tree information.

Implementation Notes

• Arithmetic sequence sum: The value of \(k_i\) must be properly bounded to ensure the harvest yield does not go below \(0\) (in this binary search, since \(X \geq 1\), only non-negative harvests are naturally counted).

• Fast I/O: Since \(N\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() or similar.

• Overflow: The total value can become very large, but since Python natively handles arbitrary-precision integers, no special care is needed.

  Source Code

import sys

def solve():
    # Use fast I/O to read all data at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: number of tree types, M: maximum total harvests
    N = int(input_data[0])
    M = int(input_data[1])
    
    # Efficiently extract F (initial yield) and D (decrease rate)
    F = list(map(int, input_data[2::2]))
    D = list(map(int, input_data[3::2]))
    FD = list(zip(F, D))
    
    # Binary search for the threshold value X.
    # We want the smallest yield value X >= 1 such that the total number of
    # harvests with yield >= X is at most M.
    # If the total number of harvests with yield >= 1 is less than or equal to M,
    # then X will be 1.
    ng = 0
    ok = 10**9 + 7 # A value larger than any possible initial yield
    
    while ok - ng > 1:
        mid = (ok + ng) // 2
        cnt = 0
        for f, d in FD:
            if f >= mid:
                # Number of harvests with yield >= mid for this tree
                cnt += (f - mid) // d + 1
                # Early break if we already exceeded M
                if cnt > M:
                    break
        if cnt <= M:
            ok = mid
        else:
            ng = mid
    
    # X is the threshold yield. We take all harvests with yield >= X.
    X = ok
    total_cnt = 0
    total_sum = 0
    
    for f, d in FD:
        if f >= X:
            # Number of harvests for this tree with yield >= X
            k = (f - X) // d + 1
            total_cnt += k
            # Sum of an arithmetic progression: (k/2) * (2*first_term - (k-1)*common_difference)
            total_sum += k * (2 * f - (k - 1) * d) // 2
            
    # If the number of harvests with yield >= X is less than M,
    # we fill the remaining harvests using the next best yield value (X-1).
    # We only care if X-1 is greater than 0.
    if X > 1:
        remaining = M - total_cnt
        # There are enough harvests with yield X-1 because count(X-1) > M
        # (due to the binary search property).
        total_sum += remaining * (X - 1)
        
    # Output the maximum possible total fruits
    sys.stdout.write(str(total_sum) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.