Description

During an experiment, Akong accidentally lost control, causing $n$ damaged spots to appear on the scorching tokamak. To prevent the power of Yatagarasu from being fully released and affecting the surface world, Satori decides to repair the tokamak.

Akong's tokamak can be abstractly seen as a straight line with Akong as the origin. The coordinates of these damaged spots are $x_1,x_2,\ldots ,x_n$.

• Satori does not want to spend too much power, so she will only choose $m$ spots out of the $n$ damaged spots to repair.

• To prevent leakage at the damaged spots, Satori will connect every pair among the chosen $m$ damaged spots with a channel.

• The cost of a channel connecting $x_i$ and $x_j$ is $\left\vert x_i - x_j \right\vert$, i.e., the straight-line distance between the two points. The total cost of a plan is defined as the sum of the costs of all channels.

Satori knows there are many ways to repair $m$ damaged spots, but now she only wants to know: among all valid plans, which plan has the strictly $k$-th largest total cost.

“Strictly $k$-th largest” means the $k$-th largest plan with no ties.

Since Satori can read minds, you only need to output the total cost of that plan.

If no plan meets the requirement, output -1.

Input Format

The first line contains three integers $n,m,k$, with the same meanings as in the statement.

The second line contains $n$ integers, the coordinates $x_i$ of the damaged spots.

Output Format

Output one integer in one line, representing the required total cost.

4 2 2
26 1 21 8 

20

2 2 2
1 5

-1

Hint

[Sample Explanation]

• For sample 1, there are $6$ plans in total:

  • $(26,1)$, total cost $25$.

  • $(26,21)$, total cost $5$.

  • $(26,8)$, total cost $18$.

  • $(1,21)$, total cost $20$.

  • $(1,8)$, total cost $7$.

  • $(21,8)$, total cost $13$.

  Obviously, the strictly second largest cost is $20$.

• For sample 2, there is $1$ plan in total:

  • $(1,5)$, total cost $4$.

  Obviously, the strictly second largest cost does not exist, so the answer is -1.

[Constraints]

This problem uses bundled testdata.

• For $100\%$ of the testdata: $1 \le n,m \le 3 \times 10 ^ 5$, $1 \le k \le 2$, $0 \le \left\vert x_i \right\vert \le 10 ^ 8$, $2 \mid m$, $m \le n$.

• Detailed Constraints:

  Subtask ID	$n \le$	Special Property	Score
  $1$	$20$	$m \le 4$	$16$
  $2$	$35$	$1 \le x_i \le 7$ and $k = 1$	$9$
  $3$		$1 \le x_i \le 7$
  $4$	$100$	$k = 1$	$16$
  $5$		None
  $6$	$3 \times 10 ^ 5$	$k = 1$	$17$
  $7$		None

Translated by ChatGPT 5