题目描述

现在有一个产出奶茶的商店。商店里有若干自动做奶茶的机器，每个机器各可以在启动$a_i$分钟后产出1份奶茶，之后可以立即进行下一次启动，再过$a_i$分钟后再产出1份奶茶，依次类推。

初始时刻所有奶茶机同时启动。你的任务是计算最早在$t$分钟产出的奶茶数量大于等于$k$份。输出时刻$t$。保证答案$t \le 10^{18}$。

输入格式

一行两个整数$n, k$，表示一共有$n$个奶茶机，需要产出$k$份奶茶。

接下来一行$n$个整数，依次表示每个奶茶机启动$a_i$分钟后可以产出一份奶茶。

输出格式

一行一个整数$t$，表示最早在$t$分钟后产出的奶茶数量超过$k$份。

3 3
1 1 1

1

3 3
1 2 3

2

数据规模与约定

共10个测试点，每个测试点10分。

大样例

大样例下载