← 返回题目列表

AtCoder · awc0104_b

B. 巴士到达时间

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正在车站前的巴士站等巴士。

有 N 经过此巴士站的巴士路线,高桥可搭乘其中任何路线的巴士到达目的地。沿途巴士 i (1 \leq i \leq N)以以下时间间隔运行 A_i 分钟,有时到达此巴士站 0, A_i, 2A_i, 3A_i, \ldots (以分钟为单位)。也就是说,所有路线的公交车在同一时间同时到达 0,之后各路公交车继续按照各自的间隔到达。

由于他在目的地的日程安排,如果高桥提前搭乘巴士 T (以分钟为单位),他最终会在目的地等待。因此,高桥决定搭乘最早到达该巴士站的巴士。 T (包括确切的时间 T).

考虑所有路线的公交车到达时间,找到大于或等于 time 的最早到达时间 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
  • 第一行包含一个整数 N 代表公交线路数量和一个整数 T 代表高桥愿意乘坐公交车的最早时间(以分钟为单位),中间用空格隔开。
  • 第二行包含整数 A_1, A_2, \ldots, A_N 代表每条公交路线的运营间隔(以分钟为单位),以空格分隔。

输出

一行打印在某时间或该时间之后最早到达公交车站的公交车的到达时间(以分钟为单位) T.


示例输入 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