Overview

For each plant, the height after \(D\) days can be calculated as “current height \(A_i\) + daily growth rate \(B_i \times D\).”
Summing this over all plants gives the answer.

Analysis

The key observation is that growth is independent for each plant, and moreover the growth rate is constant every day.
Therefore, the height of the \(i\)-th plant after \(D\) days can be expressed in a single formula:

\( A_i + B_i \cdot D \)

Since we want the total sum, we simply compute:

\( \sum_{i=1}^{N} (A_i + B_i \cdot D) \)

A naive “day-by-day simulation” would require updating all plants each day, resulting in a time complexity of \(O(ND)\).
Given the constraints \(N \le 10^5,\ D \le 10^6\), this leads to roughly \(10^{11}\) operations in the worst case, which is not feasible (TLE).

Instead of updating daily, by adding \(D\) days’ worth of growth all at once, each plant requires only a single calculation, yielding an \(O(N)\) solution.

Algorithm

1. Read \(N, D\).
2. Initialize the total total to 0.
3. For each plant, read \((A, B)\) and perform total += A + B * D.
4. Output total.

For example, if \(D=3\) and a plant has \((A,B)=(10,2)\), then after 3 days its height is \(10+2\times3=16\).
We apply this same process to all plants and sum the results.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (adding on the fly without storing the input)

Implementation Notes

• In Python, integers have arbitrary precision, so large values within the constraints (up to approximately \(2\times10^{16}\)) can be handled safely.

• Since the number of input lines is large, using sys.stdin.readline instead of input() for faster reading is effective.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, D = map(int, input().split())
    total = 0
    for _ in range(N):
        A, B = map(int, input().split())
        total += A + B * D
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.