Областная олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Задача D. Разделение команды

Есть $n$ игроков которые стоят в ряд. Они хотят сыграть в игру. Для этого им нужно разделится на две команды по $k$ человек.

У $i$-го игрока $a_i$ уровень игры. Сила команды это сумма уровней всех его участников.

Вы можете выбрать $2$ * $k$ игроков которые будут играть. Но они сами поделятся на команды. В первой команде будут первые $k$ игроков которые стоят ближе к началу ряду. Во второй команде будут последние $k$ игроков.

Запишем силу первой команды как $A$ и второй как $B$.

Найдите максимальное значение $A$ - $B$.

Например, есть $6$ игроков с уровнями [$3$, $1$, $7$, $2$, $1$, $2$]. Если выбрать игроков с номерами $1$, $3$, $5$ ,$6$ то в первой команде будут игроки $1$, $3$ и сила команды $A$ = $3$ + $7$ = $10$, во второй игроки $5$, $6$ и сила команды $B$ = $1$ + $2$ = $3$. $A$ - $B$ = $10$ - $3$ = $7$.

Формат входного файла

В первой строке два целых числа $n$, $k$ ($1$ $\le$ $n$ $\le$ $10^5$, $1$ $\le$ $k$ $\le$ $\frac{n}{2}$) - колчество игроков и размер команд.

Во второй строке $n$ целых чисел $a_1$, $a_2$ $\ldots$ $a_n$ ($1$ $\le$ $a_i$ $\le$ $10^5$) - уровень игроков.

Формат выходного файла

Выведите максимальное значение $A$ - $B$.

Примеры

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

6 2
3 1 7 2 1 2

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

7

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

5 1
3 4 6 8 9

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

-1