Number Deletion Game

2000ms

524288K

Description:

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:

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$$$;
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$$$;
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:

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:

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

Sample Input:

5 2
3 4 1 5 2

Sample Output:

Sample Input:

7 3
101 108 200 1 201 109 100

Sample Output:

Informação

Provedor Codeforces

Código CF1431G