Вчитель записав на дошці числа a1,a2,...,an. Потім, доки кількість записаних чисел на дошці не досягне m, учні по одному підходять до дошки, обирають будь-які два послідовних числа, які на даний момент записані на дошці, і записують між ними суму цих двох чисел.
Знайдіть найменше можливе значення найбільшого числа, записаного на дошці.
Перший рядок містить два цілих числа n і m (2≤n≤m≤105). Наступний рядок містить n цілих чисел a1,a2,...,an (1≤ai≤106).
Виведіть найменше можливе значення найбільшого числа, записаного на дошці.
Приклад 1.
Приклад 2.