Работа роботов

На фабрике имеется n роботов. Они принадлежат к разным поколениям, поэтому на изготовление одного и того же продукта каждому требуется разное время: новые модели работают быстрее, а более старые — медленнее. При этом все роботы могут работать одновременно. Фабрике необходимо произвести X изделий. Вы, как менеджер, должны определить, какое минимальное время потребуется, чтобы изготовить эти X единиц продукции.

Входные данные

Первая строка входных данных содержит два целых числа n (1 ≤ n ≤ ) и X (1 ≤ X ≤ ).

Во второй строке указаны n целых чисел , разделённые пробелами, где каждое число означает время, необходимое конкретному роботу для производства одного изделия (1 ≤ ).

Выходные данные

Программа должна вывести минимальное время, за которое можно успеть произвести X изделий.

Примеры

Входные данные

Выходные данные

3 8
4 2 5

10

Пояснение

  1. Первая машина сделает 2 изделия (время=8), вторая — 5 изделий (время=10), а третья — 1 изделие (время=5). Итого получается 10 изделий.

  2. Первая машина сделает 2 изделия (время=8), вторая — 4 изделия (время=8), а третья — 2 изделия (время=10). Итого получается 10 изделий.

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue