/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は駅前のバス停でバスを待っています。
このバス停には N 系統のバス路線が通っており、どの路線のバスに乗っても高橋君の目的地に行くことができます。バス路線 i（1 \leq i \leq N）のバスは A_i 分間隔で運行されており、時刻 0, A_i, 2A_i, 3A_i, \ldots（分）にこのバス停に到着します。すなわち、すべてのバス路線のバスが時刻 0 に同時に到着し、その後はそれぞれの間隔で到着し続けます。
高橋君は目的地での用事の都合上、時刻 T（分）より前にバスに乗っても目的地で待つだけになってしまいます。そこで高橋君は、時刻 T 以降（時刻 T ちょうどを含む）にこのバス停に最も早く到着するバスに乗ることにしました。
すべてのバス路線のバス到着時刻を合わせて考えたとき、時刻 T 以上であるもののうち最も早い到着時刻を求めてください。
制約
- 1 \leq N \leq 10^5
- 0 \leq T \leq 10^9
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N T A_1 A_2 \ldots A_N
- 1 行目には、バス路線の系統数を表す整数 N と、高橋君がバスに乗り始めてもよい最も早い時刻（分）を表す整数 T が、スペース区切りで与えられる。
- 2 行目には、各バス路線の運行間隔（分）を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
時刻 T 以降で最も早くバス停に到着するバスの到着時刻（分）を 1 行に出力せよ。
入力例 1
3 10 3 5 7
出力例 1
10
入力例 2
2 0 4 6
出力例 2
0
入力例 3
5 1000000000 3 7 11 13 17
出力例 3
1000000001
Score : 300 pts
Problem Statement
Takahashi is waiting for a bus at the bus stop in front of the station.
There are N bus routes that pass through this bus stop, and Takahashi can reach his destination by taking a bus on any of these routes. Buses on route i (1 \leq i \leq N) operate at intervals of A_i minutes, arriving at this bus stop at times 0, A_i, 2A_i, 3A_i, \ldots (in minutes). In other words, buses on all routes arrive simultaneously at time 0, and after that, each route's buses continue to arrive at their respective intervals.
Due to his schedule at the destination, if Takahashi takes a bus before time T (in minutes), he would just end up waiting at the destination. Therefore, Takahashi has decided to take the bus that arrives at this bus stop earliest at or after time T (including exactly time T).
Considering the arrival times of buses across all routes, find the earliest arrival time that is greater than or equal to time T.
Constraints
- 1 \leq N \leq 10^5
- 0 \leq T \leq 10^9
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
N T A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of bus routes and an integer T representing the earliest time (in minutes) at which Takahashi is willing to take a bus, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the operating intervals (in minutes) of each bus route, separated by spaces.
Output
Print on one line the arrival time (in minutes) of the bus that arrives at the bus stop earliest at or after time T.
Sample Input 1
3 10 3 5 7
Sample Output 1
10
Sample Input 2
2 0 4 6
Sample Output 2
0
Sample Input 3
5 1000000000 3 7 11 13 17
Sample Output 3
1000000001