Overview

This is a problem where you calculate the number of days required for each plant to reach a height of at least \(M\) cm, and output the maximum of those values.

Analysis

The height of each plant \(i\) on day \(d\) is \(A_i + B_i d\). The observation ends when “all plants satisfy \(A_i + B_i d \ge M\)”, which can be rephrased as:

• For each plant, find the “minimum number of days \(d_i\) to reach \(M\)”,
• For all plants to be ready, \(d \ge d_i\) must hold for every plant,
• Therefore, the minimum \(d\) is \(\max_i d_i\).

If you naively increment \(d=0,1,2,\dots\) and check all plants each time, it won’t finish in time when the answer \(d\) is large (which can be on the order of \(10^9\)), resulting in TLE.

The key insight is to directly compute the required number of days for each plant using a formula.

The condition for plant \(i\) to reach \(M\) is: - If \(A_i \ge M\), it’s already achieved from the start, so \(d_i = 0\). - If \(A_i < M\), then from \(A_i + B_i d \ge M\): \(d \ge \dfrac{M-A_i}{B_i}\) However, since \(d\) must be an integer, we need to take the ceiling.

The ceiling can be computed using integer arithmetic as: [ d_i = \left\lceil \frac{M-A_i}{B_i} \right\rceil = \frac{(M-A_i) + (B_i-1)}{B_i} ] (using integer division).

Concrete example: When \(A=3, B=2, M=8\), \(M-A=5\), \(\lceil 5/2\rceil=3\) days are needed (day 0: 3cm → day 3: 9cm).

Algorithm

1. Initialize the answer ans to \(0\).
2. For each plant \((A_i, B_i)\):
   • If \(A_i \ge M\), the required number of days is \(0\), so skip (no need to update ans).
   • If \(A_i < M\), compute [ need = \left\lceil \frac{M-A_i}{B_i} \right\rceil = \frac{(M-A_i) + (B_i-1)}{B_i} ] and set ans = max(ans, need).
3. Output ans.

In the end, ans equals \(\max_i d_i\), which is the minimum number of days for all plants to reach at least \(M\).

Complexity

• Time complexity: \(O(N)\) (each plant is processed once)
• Space complexity: \(O(1)\) (processing while reading input, without storing an array)

Implementation Notes

• For ceiling division, use need = (M - A + B - 1) // B (only when \(A < M\)).

• If \(A \ge M\), using this formula could mix in negative numbers and produce unintended results, so it’s safer to branch as shown in the code.

• Since the constraints are large, use sys.stdin.readline for fast input.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    ans = 0
    for _ in range(N):
        A, B = map(int, input().split())
        if A < M:
            need = (M - A + B - 1) // B
            if need > ans:
                ans = need
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.