Учитель написал на доске числа $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 $$