Вчитель записав на дошці числа $a_1, a_2, ..., a_n$. Потім, доки кількість записаних чисел на дошці не досягне $m$, учні по одному підходять до дошки, обирають будь-які два послідовних числа, які на даний момент записані на дошці, і записують між ними суму цих двох чисел. Знайдіть найменше можливе значення найбільшого числа, записаного на дошці. \InputFile Перший рядок містить два цілих числа $n$ і $m~(2 \le n \le m \le 10^5)$. Наступний рядок містить $n$ цілих чисел $a_1, a_2, ..., a_n~(1 \le a_i \le 10^6)$. \OutputFile Виведіть найменше можливе значення найбільшого числа, записаного на дошці. \Examples Приклад 1. $$ 1, 1 → 1, 𝟐, 1 → 1, 𝟑, 2, 1 → 1, 3, 2, 𝟑, 1 $$ Приклад 2. $$ 4, 6, 3 → 4, 6, 𝟗, 3 $$