Overview

This problem asks us to find the total value when selecting at most \(M\) items with the highest values from the “harvest sequences” (arithmetic sequences) produced by each tree. Instead of explicitly enumerating the sequences, we solve this using binary search by counting “the number of values at or above a threshold.”

Analysis

Key Observation

The harvest amount from tree \(i\) on the \(k\)-th harvest is
\(\max(F_i-(k-1)D_i,\,0)\)
so looking only at the positive part, we get the arithmetic sequence:

• \(F_i,\, F_i-D_i,\, F_i-2D_i,\,\dots\)

(terminating once the value becomes \(0\) or less).

Therefore, the problem can be rephrased as:

Collect all (positive) harvest amounts from every tree into one large multiset, then take the top \(M\) values and compute their sum.

Why a Naive Approach Fails

• Each tree can be harvested up to \(M\) times.
• For example, using a priority queue to extract the “next largest harvest” \(M\) times would be \(O(M\log N)\), which looks promising at first glance, but we essentially want to compute “the sum of the top \(M\) values overall” efficiently (and the implementation tends to have heavy constants).
• Furthermore, enumerating all harvest amounts is \(O(NM)\) in the worst case, which is far too slow.

Solution Strategy (Counting with a Threshold)

Consider a function that counts “how many total harvest amounts are at least \(x\).”

For tree \(i\), when \(x \le F_i\): - \(F_i-(k-1)D_i \ge x\) - \(\Rightarrow (k-1) \le \dfrac{F_i-x}{D_i}\) - So the count is \(k = \left\lfloor\dfrac{F_i-x}{D_i}\right\rfloor + 1\)

Summing this over all trees gives us “the number of values \(\ge x\)” in \(O(N)\).

Since: - As \(x\) increases, “the number of values \(\ge x\)” monotonically decreases

we can use binary search to find “the threshold value that serves as the boundary for the top \(M\) items.”

Algorithm

1. First, count the total number of positive harvest amounts \(total\_pos\).
   • If \(total\_pos \le M\), all positive harvest amounts can be taken, so the answer is “the sum of all positive harvest amounts.”
2. Otherwise, use binary search to find the maximum \(x\) such that:
   • Condition: “There are at least \(M\) harvest amounts with value \(\ge x\)”
   • That is, the maximum \(x\) satisfying count_ge(x) >= M.
3. Using the found \(x\) as the boundary, construct the answer as follows:
   • Sum all harvest amounts strictly greater than \(x\) (i.e., \(\ge x+1\)). Let the count be \(cnt\_gt\) and the sum be \(sum\_gt\).
   • Fill the remaining \(M - cnt\_gt\) slots with harvest amounts of exactly value \(x\).
     (By the definition of the binary search, there are at least \(M\) values \(\ge x\), so exactly \(x\) exists in sufficient quantity.)
   • Thus the final answer is
     \(ans = sum\_gt + (M - cnt\_gt) \times x\)

Sum Calculation (Arithmetic Series Sum)

When tree \(i\) has \(k\) terms with value \(\ge x\), the last term is
\(last = F_i-(k-1)D_i\)
and the sum is the arithmetic series sum
\(\dfrac{k(F_i+last)}{2}\)
This is summed over all trees and computed as count_sum_ge(x).

Complexity

• Time complexity: \(O(N \log(\max F_i))\)
  (Binary search runs \(\log(\max F_i)\) times, each iteration aggregating in \(O(N)\))
• Space complexity: \(O(N)\)
  (Storing the arrays \(F_i, D_i\))

Implementation Notes

• Boundary handling: By first summing everything strictly greater than \(x\) (\(\ge x+1\)) and then filling the remainder with \(x\), we count without duplication.

• Overflow: Python’s int is arbitrary precision so it’s safe, but the sums can become very large (on the order of \(10^9 \times 2\times 10^5\)), so int64 is essential in other languages.

• Fast input: Since \(N\) can be \(2\times 10^5\), reading all input at once with sys.stdin.buffer.read() ensures stable and fast performance.

  Source Code

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    N, M = it[0], it[1]
    Fs = [0] * N
    Ds = [0] * N
    mx = 0
    idx = 2
    for i in range(N):
        f = it[idx]; d = it[idx + 1]
        idx += 2
        Fs[i] = f
        Ds[i] = d
        if f > mx:
            mx = f

    def count_ge(x: int) -> int:
        tot = 0
        for f, d in zip(Fs, Ds):
            if f >= x:
                tot += (f - x) // d + 1
        return tot

    def count_sum_ge(x: int):
        totc = 0
        tots = 0
        for f, d in zip(Fs, Ds):
            if f >= x:
                k = (f - x) // d + 1
                last = f - (k - 1) * d
                tots += k * (f + last) // 2
                totc += k
        return totc, tots

    total_pos = count_ge(1)
    if total_pos <= M:
        _, s = count_sum_ge(1)
        print(s)
        return

    lo, hi = 1, mx + 1  # find largest x with count_ge(x) >= M
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if count_ge(mid) >= M:
            lo = mid
        else:
            hi = mid

    x = lo
    cnt_gt, sum_gt = count_sum_ge(x + 1)  # terms strictly greater than x
    ans = sum_gt + (M - cnt_gt) * x
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.