The following languages are only available languages for the problems from the contest

Kotlin Heroes 5: ICPC Round:

- Kotlin 1.6.10
- Kotlin 1.7.20

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Number Deletion Game

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputAlice 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).

Examples

Input

5 2 3 4 1 5 2

Output

4

Input

7 3 101 108 200 1 201 109 100

Output

283

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/29/2023 18:04:16 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|