Динамический массив

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

Учитель написал на доске числа $a_{1}, a_{2}, ..., a_{n}$ . Затем, пока количество написанных на доске чисел не достигнет $m$ , учащиеся по одному подходят к доске, выбирают любые два последовательных числа, написанных в данный момент на доске, и записывают между ними сумму этих двух чисел.

Найдите наименьшее возможное значение самого большого числа, написанного на доске.

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

Первая строка содержит два целых числа $n$ и $m (2 \leq n \leq m \leq 1 0^{5})$ . Следующая строка содержит $n$ целых чисел $a_{1}, a_{2}, ..., a_{n} (1 \leq a_{i} \leq 1 0^{6})$ .

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

Выведите наименьшее возможное значение наибольшего числа, написанного на доске.

Примеры

Пример 1.

1, 1 \to 1, 2, 1 \to 1, 3, 2, 1 \to 1, 3, 2, 3, 1

Пример 2.

4, 6, 3 \to 4, 6, 9, 3

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Ввод #3

Ответ #3

Отправки 333

Коэффициент принятия 25 %