Для школьного праздника нужно изготовить не менее K игрушек. На фабрике есть N автоматов. Автомат с номером i изготавливает одну игрушку за Ai минут.
Все автоматы начинают работу одновременно в момент времени 0 и работают независимо друг от друга. Закончив игрушку, автомат сразу начинает следующую. Материалов достаточно, готовых игрушек в начале нет.
Игрушка учитывается только после полного завершения работы над ней. Например, автомат, которому нужны 3 минуты, выпускает игрушки в моменты 3, 6, 9 минут и так далее.
Найдите минимальное время, за которое будет готово не менее K игрушек.
Входные данные
В первой строке записаны два целых числа N K — количество автоматов и необходимое количество игрушек.
Во второй строке записаны N целых чисел A1, A2, …, AN — время изготовления одной игрушки каждым автоматом.
1 ≤ N ≤ 1000; 1 ≤ K ≤ 109; 1 ≤ Ai ≤ 106.
Выходные данные
Выведите одно целое число — минимальное время в минутах.
| № | Входные данные | Выходные данные |
|
1
|
3 7
2 3 4
|
8
|
|
2
|
2 1
5 7
|
5
|