Динамічний масив

Вчитель записав на дошці числа $a_1,a_2,...,a_n$. Потім, доки кількість записаних чисел на дошці не досягне $m$, учні по одному підходять до дошки, обирають будь-які два послідовних числа, які на даний момент записані на дошці, і записують між ними суму цих двох чисел.

Знайдіть найменше можливе значення найбільшого числа, записаного на дошці.

Вхідні дані

Перший рядок містить два цілих числа $n$ і $m(2\le n\le m\le 10^5)$. Наступний рядок містить $n$ цілих чисел $a_1,a_2,...,a_n(1\le a_i\le 10^6)$.

Вихідні дані

Виведіть найменше можливе значення найбільшого числа, записаного на дошці.

Приклади

Приклад 1.

Приклад 2.