Overview

Since each bus route arrives at regular intervals, the problem asks us to find the first bus arriving at or after time \(T\) (the earliest arrival among all routes).

Analysis

Bus route \(i\) runs at intervals of \(A_i\) minutes, so its arrival times are
\(0, A_i, 2A_i, 3A_i, \ldots\) — that is, multiples of \(A_i\).

Therefore, to find “the first arrival time at or after time \(T\)”, we compute for each \(A_i\): - The smallest multiple of \(A_i\) that is at least \(T\)

and then take the minimum among all of them.

A naive approach of “incrementing one minute at a time from time \(T\) and checking whether any route arrives” would result in over \(10^9\) loop iterations in the worst case since \(T\) can be up to \(10^9\), which will not finish in time (causing TLE).

The key insight is that for each route, the “next arrival” can be computed directly.

Example: When \(T=13, A_i=5\)
The arrivals are \(0,5,10,15,20,\ldots\), so the first one at or after \(13\) is \(15\).
This is obtained by taking the ceiling of dividing \(13\) by \(5\) and then multiplying back.

Algorithm

For each route’s interval \(a(=A_i)\), find the smallest multiple \(t\) of \(a\) that is at least \(T\).

• \(t = \left\lceil \frac{T}{a} \right\rceil \cdot a\)

The ceiling division using integer arithmetic can be written as: - \(\left\lceil \frac{T}{a} \right\rceil = \frac{T + a - 1}{a}\) (integer division)

Therefore: - \(t = \left( \frac{T + a - 1}{a} \right) \cdot a\)

Compute this for all routes and output the minimum \(t\) as the answer.

Complexity

• Time complexity: \(O(N)\) (each route is processed once)
• Space complexity: \(O(1)\) (constant aside from the input array)

Implementation Notes

• The ceiling calculation is safe and concise when written as ((T + a - 1) // a) * a.

• Initialize the answer to a sufficiently large number (e.g., 10**30) and update with the minimum.

• Since \(N\) can be up to \(10^5\), using sys.stdin.readline in Python speeds up input reading.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, T = map(int, input().split())
    A = list(map(int, input().split()))
    ans = 10**30
    for a in A:
        t = ((T + a - 1) // a) * a
        if t < ans:
            ans = t
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.