题目描述

有 $n$ 台机器同时开始生产。第 $i$ 台机器每 $a_i$ 分钟可以产出一件产品，产出后立即开始下一轮生产。

初始时刻所有机器同时启动。请求出最早在 $t$ 分钟后，累计生产的产品数量不少于 $k$ 件的最小的 $t$。

输入格式

第一行两个整数 $n, k$，分别表示机器数量和需要生产的产品数量。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每台机器的生产间隔。

输出格式

一行一个整数 $t$，表示最早达到 $k$ 件产品的时刻。

样例

3 3
1 2 3

2

3 10
10 20 30

60

5 100
1 1 1 1 1

20

样例解释

对于样例 1：第 0 分钟启动，第 1 分钟第 1 台产 1 件，第 2 分钟第 1 台再产 1 件、第 2 台产 1 件，此时共 3 件，故 $t=2$。

对于样例 2：在时刻 $t$，第 $i$ 台机器生产了 $\lfloor t/a_i \rfloor$ 件。

• $t=30$：$\lfloor 30/10 \rfloor + \lfloor 30/20 \rfloor + \lfloor 30/30 \rfloor = 3+1+1=5$
• $t=40$：$4+2+1=7$
• $t=50$：$5+2+1=8$
• $t=60$：$6+3+2=11 \ge 10$，故最早时刻为 $t=60$。

对于样例 3：所有 $a_i = 1$，每台每分钟产 1 件。$n=5$ 台共每分钟 5 件，需要 $k=100$ 件，$t = k/n = 20$。

数据范围与约定

下发样例

下发样例下载