Overview

For each plant, the height after \(D\) days is the “current height \(A_i\)” plus the “growth over \(D\) days \(D \times B_i\)”.
Summing this over all plants gives the answer.

Analysis

What we want to find in this problem is the total height of \(N\) plants after \(D\) days.

First, focusing on a single plant, its current height is \(A_i\) mm and it grows \(B_i\) mm per day, so its height after \(D\) days is

\(A_i + D \times B_i\)

Therefore, the overall total is

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

Key Insight

The key point of this problem is that “there is no need to simulate day by day.”

For example, if we naively consider: - On day 1, grow all plants - On day 2, grow all plants - … - Repeat until day \(D\)

the time complexity would be \(O(ND)\).

Given the constraints: - \(N \le 10^5\) - \(D \le 10^6\)

this would require up to about \(10^{11}\) operations in the worst case, which is not practical.

However, since each plant’s growth rate is constant, we can directly calculate the height after \(D\) days.
This means we only need to compute once for each plant.

Concrete Example

For example, for a plant with \(A=10\), \(B=3\), \(D=5\):

• After 1 day: \(13\)
• After 2 days: \(16\)
• After 3 days: \(19\)
• After 4 days: \(22\)
• After 5 days: \(25\)

But this can be computed directly from the start as:

\(10 + 5 \times 3 = 25\)

Algorithm

1. Read \(N\) and \(D\).
2. Initialize the total total to \(0\).
3. For each plant, read the current height \(A\) and the daily growth rate \(B\).
4. Add the plant’s height after \(D\) days, \(A + D \times B\), to total.
5. Finally, output total.

With this method, the answer is obtained by looking at each plant just once.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• For each plant, simply accumulate A + D * B.

• The answer can be large, but the problem statement guarantees it does not exceed \(2 \times 10^{16}\).

• Python’s integer type can handle large values, so there are no issues as-is.

• Since the input can be large, using sys.stdin.readline allows for faster processing.

  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 + D * B
    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.