Tokamak Repair

In a scientific experiment, Akong’s tokamak lost control and developed n damages along a line (abstractly represented as positions on a number line, with Akong at the origin). The coordinates of the damages are given as \( x_1,x_2,\dots,x_n \). To minimize the power consumption, Jue will repair only m out of these n damages. In order to prevent leakage at the damaged positions, Jue connects every pair among the chosen m damages with a channel.

The cost of a channel connecting two damages at \( x_i \) and \( x_j \) is \( |x_i-x_j| \) (i.e. the absolute difference between the coordinates). The total cost of a repair scheme (i.e. a choice of m damages) is defined as the sum of the costs of all channels connecting the chosen damages. Note that if the chosen damages (in increasing order) are \( a_1,a_2,\dots,a_m \), then the cost can be computed by the formula:

[ Cost = \sum_{1\le i < j \le m} (a_j - a_i) = \sum_{p=1}^{m} (2p - m - 1),a_p. ]

There are many possible ways to choose m damages from the available n points. Jue is interested in the scheme whose total cost is the strictly k-th largest (i.e. when the distinct total cost values are sorted in descending order, the cost at the k-th position). If no such scheme exists, output -1.

inputFormat

The input begins with a line containing three integers \( n, m, k \) where \( 1 \le m \le n \). The next line contains \( n \) integers \( x_1,x_2,\dots,x_n \), representing the coordinates of the damages.

outputFormat

Output a single integer: the total cost of the scheme which is the strictly k-th largest among all valid repair schemes. If no such scheme exists, output -1.

sample

4 2 1
1 3 6 10

9