G. Игра с удалением чисел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У них есть множество, который изначально состоит из $$$n$$$ целых чисел. Игра длится $$$k$$$ ходов. Во время каждого хода происходит следующее:

  1. сначала Алиса выбирает целое число из множества. Она может выбрать любое целое число кроме максимального. Пусть целое число, выбранное Алисой, равно $$$a$$$;
  2. затем Боб выбирает целое число из множества. Он может выбрать любое целое число которое больше $$$a$$$. Пусть целое число, выбранное Бобом, равно $$$b$$$;
  3. наконец, и $$$a$$$, и $$$b$$$ удаляются из множества, а значение $$$b - a$$$ добавляется к счету игры.

Изначально счет игры равен $$$0$$$. Алиса хочет максимизировать итоговый счет, а Боб хочет минимизировать его. Предположив, что и Алиса, и Боб играют оптимально, вычислите итоговый счет игры.

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

Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 400$$$, $$$1 \le k \le \lfloor\frac{n}{2}\rfloor$$$) — начальный размер множества и количество ходов в игре.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — стартовое содержимое множества. Это попарно различные целые числа.

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

Выведите одно целое число — итоговый счет игры (при условии, что и Алиса, и Боб играют оптимально).

Примеры
Входные данные
5 2
3 4 1 5 2
Выходные данные
4
Входные данные
7 3
101 108 200 1 201 109 100
Выходные данные
283