Overview

This is a problem where you calculate the height of each of the \(N\) plants after \(D\) days and output their total sum.

Analysis

The \(i\)-th plant has a current height of \(A_i\) and grows by \(B_i\) millimeters per day. Therefore, its height after \(D\) days can be expressed by the following formula:

\[A_i + B_i \times D\]

For example, if a plant has a current height of \(10\) mm and grows \(3\) mm per day, its height after \(5\) days is \(10 + 3 \times 5 = 25\) mm.

The total height of all \(N\) plants is:

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

Some people might consider a naive approach of “simulating day by day.” That is, looping through \(D\) days and updating the height of every plant each day. In this case, the time complexity would be \(O(N \times D)\), and when \(N = 10^5\) and \(D = 10^6\), this requires \(10^{11}\) operations, resulting in TLE (Time Limit Exceeded).

However, since the growth rate is constant, the height after \(D\) days can be directly calculated with a single multiplication. There is no need to simulate day by day.

Algorithm

1. Initialize a variable total to \(0\) to hold the sum.
2. For each plant \(i\), add the height after \(D\) days, \(A_i + B_i \times D\), to total.
3. Output total.

Concrete example (sample input):

3 2
10 5
20 3
15 8

• Plant 1: \(10 + 5 \times 2 = 20\)
• Plant 2: \(20 + 3 \times 2 = 26\)
• Plant 3: \(15 + 8 \times 2 = 31\)
• Total: \(20 + 26 + 31 = 77\)

Complexity

• Time complexity: \(O(N)\) — only one calculation per plant
• Space complexity: \(O(1)\) — only a variable to hold the total sum is used

Implementation Notes

• Watch out for overflow: \(A_i\) can be up to \(10^9\), \(B_i \times D\) can be up to \(10^5 \times 10^6 = 10^{11}\), and since there are up to \(N = 10^5\) plants, the total can reach approximately \(10^{16}\). In Python, integer overflow does not occur, but if you use C++ or similar languages, you need to use the long long type.

• No simulation needed: Since growth is at a constant rate, the height after \(D\) days can be directly computed as \(A_i + B_i \times D\). There is no need to advance one day at a time in a loop.

  Source Code

N, D = map(int, input().split())
total = 0
for _ in range(N):
    a, b = map(int, input().split())
    total += a + b * D
print(total)

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