Учитель информатики хочет записать видео со школьного концерта на N DVD-дисков. В его распоряжении имеется компьютерный класс, содержащий K компьютеров с пишущими DVD-приводами. Видеофайлы заранее скопированы по сети на все компьютеры.

К сожалению, разные компьютеры приобретались в разное время, имеют разное оборудование, и потому диски пишут с разной скоростью. Требуется определить, какое минимальное время потребуется, чтобы записать все диски.

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

В первой строке входных данных записаны через пробел два числа N и K (1 ≤ N, K ≤ 10⁵).

В следующей строке записаны через пробел K целых чисел T₁, T₂, ..., T_k − время записи одного DVD-диска на каждом компьютере (1 ≤ T_i ≤ 10⁵).

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

Одно натуральное число − минимальное количество минут, которое потребуется для записи всех N дисков.

Пример ввода 3 2 10 15 Пример вывода 20

 Система оценивания.

Подзадача 1 (до 50 баллов): 1 ≤ N, K, T_i ≤ 1000.

Подзадача 2 (до 50 баллов): 1 ≤ N, K, T_i ≤ 10⁵.