Громозека играет в одиночную игру, используя числовую прямую и
N фишек. Каждая из фишек расположена в некоторой целочисленной координате. Заметьте, несколько фишек могут быть размещены в одной и той же координате.
Цель игры: посетить фишками все
M координат
X1,
X2, ...,
XM, повторив следующий ход.
Ход: выберите фишку с координатой
X. Поместите эту фишку в координату
X+1 или
X-1.
Обратите внимание, что координаты, где мы первоначально размещены фишки, уже считаются посещенными.
Найдите минимальное количество ходов, необходимое для достижения цели.
Входные данные
В первой строке программа получает на вход два целых числа:
N и
M (1 <= N, M <= 10
5). Во второй строке записаны
M целых чисел
X1,
X2, ...,
XM (-10
5 <= X
i <= 10
5). Все числа
Xi различны.
Выходные данные
Выведите на экран ответ на задачу.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
2 5
10 12 1 2 14 |
5 |
Цель может быть достигнута за пять ходов следующим образом, и это минимально необходимое количество ходов.
Сначала поместите две фишки в координаты 1 и 10.
Переместите фишку с координатой 1 на 2.
Переместите фишку с координатой 10 на 11.
Переместите фишку с координатами 11 на 12.
Переместите фишку с координатами 12 на 13.
Переместите фишку с координатами 13 на 14. |
| 2 |
3 7
-10 -3 0 9 -100 2 17 |
19 |
|
| 3 |
100 1
-100000 |
0 |
|