Overview

\(N\) plants each have distinct initial heights \(A_i\) and daily growth rates \(B_i\). The problem asks to find the first day (the minimum non-negative integer \(d\)) when all plants have a height of at least \(M\) cm.

Analysis

To find “the day when all plants reach height \(M\) or more,” we first consider “how many days does each individual plant need to reach height \(M\) or more?”

For plant \(i\), the height on day \(d\) is \(A_i + B_i \times d\). The condition for this to be at least \(M\) is as follows: $\(A_i + B_i \times d \geq M\)$

Solving this inequality for \(d\): 1. If \(A_i \geq M\) already: the condition is satisfied at \(d = 0\) days. 2. If \(A_i < M\): $\(B_i \times d \geq M - A_i\)\( \)\(d \geq \frac{M - A_i}{B_i}\)$

Since \(d\) must be an integer, the minimum integer \(d_i\) satisfying the condition is the ceiling of \(\frac{M - A_i}{B_i}\).

For all plants to satisfy the condition, the answer is the maximum value among the required days \(d_i\) for each plant.

Algorithm

1. Initialize the answer variable max_d to \(0\).
2. For each plant \(i = 1, 2, \ldots, N\), repeat the following:
   • If \(A_i < M\):
     • Compute \(d_i = \lceil \frac{M - A_i}{B_i} \rceil\).
     • Compare max_d with \(d_i\), and update max_d to the larger value.
3. Output the final max_d.

Complexity

• Time complexity: \(O(N)\) Since we loop once for each of the \(N\) plants, the problem can be solved in linear time.
• Space complexity: \(O(N)\) This is \(O(N)\) if all input values are stored in a list. It can be reduced to \(O(1)\) if values are read and processed one at a time.

Implementation Notes

Ceiling Division

In integer arithmetic in programming, to compute the ceiling of \(X / Y\) (\(\lceil X/Y \rceil\)) for positive numbers \(X, Y\), the following technique is commonly used:

# (X + Y - 1) // Y
d = (M - A + B - 1) // B

This allows computing the ceiling using only error-free integer arithmetic without using floating-point numbers (float).

Fast Input

When processing input of size \(N = 2 \times 10^5\) in Python, repeatedly calling input() can result in long execution times. By reading all input at once using sys.stdin.read().split(), execution time can be significantly reduced.

Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペースや改行で分割してリストにする
    # Nが2*10^5程度であれば、この方法がPythonでは高速です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して順番に値を取得する
    it = iter(input_data)
    N = int(next(it))
    M = int(next(it))
    
    max_d = 0
    for _ in range(N):
        A = int(next(it))
        B = int(next(it))
        
        # すでに高さがM以上の場合は、必要な日数は0日
        # 高さ A + B * d >= M となる最小の非負整数 d を求める
        if A < M:
            # A + B * d >= M
            # B * d >= M - A
            # d >= (M - A) / B
            # 最小の整数 d は ceil((M - A) / B)
            # 整数演算では (x + y - 1) // y で切り上げを計算できる
            d = (M - A + B - 1) // B
            if d > max_d:
                max_d = d
    
    # すべての植物が条件を満たす最小の日数は、各植物が必要とする日数の最大値
    print(max_d)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-preview.