Number Deletion Game
Contest: Kotlin Heroes 5: ICPC Round
Difficulty rating: 2100
Tags: *special, dp, games, greedy

Alice and Bob play a game. They have a set that initially consists of $$$n$$$ integers. The game is played in $$$k$$$ turns. During each turn, the following events happen:

1. firstly, Alice chooses an integer from the set. She can choose any integer except for the maximum one. Let the integer chosen by Alice be $$$a$$$;
2. secondly, Bob chooses an integer from the set. He can choose any integer that is greater than $$$a$$$. Let the integer chosen by Bob be $$$b$$$;
3. finally, both $$$a$$$ and $$$b$$$ are erased from the set, and the value of $$$b - a$$$ is added to the score of the game.

Initially, the score is $$$0$$$. Alice wants to maximize the resulting score, Bob wants to minimize it. Assuming that both Alice and Bob play optimally, calculate the resulting score of the game.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 400$$$, $$$1 \le k \le \lfloor\frac{n}{2}\rfloor$$$) — the initial size of the set and the number of turns in the game.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the initial contents of the set. These integers are pairwise distinct.

Output format:
Print one integer — the resulting score of the game (assuming that both Alice and Bob play optimally).

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
5 2
3 4 1 5 2

Example output:
4

Example input:
7 3
101 108 200 1 201 109 100

Example output:
283

Editorial:
The key observation is that Bob should always remove the minimum integer that is greater than $$$a$$$ on his turn (proving that formally is a bit complicated, but it works). So, if we sort the array $$$a$$$, after Alice removes the number $$$a_i$$$, Bob removes the number that was after $$$a_i$$$.
So, if we sort the array $$$a$$$, should we find $$$k$$$ non-intersecting pairs $$$(a_i, a_{i + 1})$$$ such that the sum of $$$a_{i + 1} - a_i$$$ is maximum possible? Unfortunately, this is suboptimal because when an element is deleted, the numeration of other elements changes. For example, if $$$n = 4$$$, $$$a = [1, 2, 3, 4]$$$, the optimal plan for Alice is:
1. erase $$$2$$$, so Bob is forced to erase $$$3$$$;
2. erase $$$1$$$, so Bob is forced to erase $$$4$$$.
How to handle these renumerations? Suppose Alice has deleted the number $$$a_i$$$ from the original sorted array, and Bob has deleted the number $$$a_{i + 1}$$$. Then, if Alice deletes $$$a_{i - 1}$$$, Bob is forced to delete $$$a_{i + 2}$$$, and so on. Thus, in $$$x$$$ turns, Alice may delete the left half of some segment of length $$$2x$$$, and force Bob to delete the right half of this segment.
It can be modeled with the following dynamic programming solution: let $$$dp_{i, j}$$$ be the maximum answer if Alice considered the first $$$i$$$ numbers and deleted $$$j$$$ of them (and Bob deleted $$$j$$$ of them as well). We can either skip the following number, transitioning from $$$dp_{i, j}$$$ to $$$dp_{i + 1, j}$$$, or delete some segment of length $$$2x$$$, transitioning from $$$dp_{i, j}$$$ to $$$dp_{i + 2x, j + x}$$$ (while adding $$$\sum\limits_{c = i + x}^{i + 2x - 1} a_c - \sum\limits_{c = i}^{i + x - 1} a_c$$$ to the value of dynamic programming). These sum queries can be performed with prefix sums in $$$O(1)$$$, so overall this solution runs in $$$O(n k^2)$$$.