Столяр работает с деревянной палкой длины L. На палке отмечены k точек, в которых необходимо сделать распилы.

За один распил столяр платит столько, какова длина того куска палки, который он распиливает в данный момент. После каждого распила один кусок делится на два меньших, и следующие распилы уже выполняются внутри получившихся частей.

Столяр может выбирать порядок распилов произвольно. От этого порядка зависит общая стоимость работы.

Требуется определить минимальную возможную суммарную стоимость всех распилов.

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

Первая строка содержит целое число L — длину палки.

Вторая строка содержит целое число k — количество необходимых распилов.

В третьей строке содержатся k различных целых чисел — позиции распилов. Каждая из них строго больше 0 и строго меньше L.

Ввод осуществляется через стандартный ввод.

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

Выведите одно целое число — минимальную суммарную стоимость всех распилов.

Вывод осуществляется через стандартный вывод.

Ограничения

• 1 <= L <= 10^9
• 1 <= k <= 100
• все позиции распилов различны
• каждая позиция распила находится строго внутри палки

Ответ может не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

7
4
1 3 4 5

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

16

Пример 2

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

7
2
1 6

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

13