Problem 657: cancer

After extensively studying the finches from the Galápagos Islands, Charles Darwin has set his sights on the members of the genus Cancer. To that end, he's keeping several species of crab. Currently, he has $N$ crabs, which he has ordered in some way from $1$ to $N$ according to several characteristics, such as size, color, smell, etc. Furthermore, all crabs are at least a little aggressive, so each crab $i$ has aggressiveness $A_{i}$ , where $A_{i}$ is positive.

Darwin also owns $K$ aquariums, where he wants to keep his crabs, in order to observe them in their natural habitat. However, he's already spent a lot of time ordering the crabs by their characteristics, so he doesn't want to break the order too much. Therefore, he's decided to put the first $T_{1}$ crabs in the first aquarium, the next $T_{2}$ crabs in the second one, and so on until the last $T_{K}$ crabs - in the last aquarium. Obviously, $T_{1} + T_{2} + \ldots + T_{K} = N$ and each $T_{i}$ is a non-negative integer, but other than that the values of all $T_{i}$ can be freely chosen by Darwin.

However, crabs have emotions too, and in particular - fear. In fact, they are quite afraid of each other, especially of the more aggressive ones. More concretely, crab $i$ is afraid of all other crabs kept in the same aquarium as $i$ , and that amount of fear towards each such crab $j$ is equal to its aggressiveness $A_{j}$ . Therefore, the total amount of fear crab $i$ feels is equal to the sum of all $A_{j}$ , where $j$ are the other crabs kept in the same aquarium as $i$ .

Darwin doesn't want to stress his crabs out too much though - each crab's individual feelings matter, after all. Thus, he's trying to minimize the total amount of fear they feel by choosing the best possible way to distribute them among the $K$ aquariums. However, back in the 30s (the 1830s that is) they didn't use to have such powerful computers, so Darwin asks you for help. Please assist him by writing a program which computes the minimum possible total amount of fear felt by the crabs when given $N$ , $K$ and all $A_{i}$ .

Input

From the first line of the standard input you should read two positive integers: $N$ and $K$ - the number of crabs and the number of aquariums. From the next line you should read $N$ positive integers: $A_{1},\ A_{2},\ldots,A_{N}$ - the aggressiveness of each of the crabs, given according to Darwin's ordering.

Output

On the only line of the standard output you should print a single non-negative integer: the minimum possible total fear felt by the crabs.

Constraints

$1 \leq K \leq N \leq 10^{5}$
$1 \leq A_{i} \leq 10^{7}$

In order to get the points for a given subtask, your solution must pass all the tests for the subtask.

Subtask 1 (11 points)

$N \leq 10$

Subtask 2 (8 points)

$N \leq 300$

Subtask 3 (12 points)

$N \leq 1 \ 000$

Subtask 4 (24 points)

$N \leq 6 \ 000$

Subtask 5 (10 points)

$N \leq 10^5$
$K = 3$

Subtask 6 (35 points)

$N \leq 10^5$

Example

stdin

8 4            
8 1 2 3 9 1 9 1

stdout

Explanation

There are $8$ crabs that we have to keep in $4$ aquariums. The optimal distribution is: crab $1$ in aquarium $1$ ; crabs $2$ , $3$ and $4$ in aquarium $2$ ; crabs $5$ and $6$ in aquarium $3$ ; crabs $7$ and $8$ in aquarium $4$ . Crab $1$ feels no fear; crab $2$ feels $5$ fear; crab $3$ feels $4$ fear; crab $4$ feels $3$ fear; crab $5$ feels $1$ fear; crab $6$ feels $9$ fear; crab $7$ feels $1$ fear; crab $8$ feels $9$ fear. The total is $0 + 5 + 4 + 3 + 1 + 9 + 1 + 9 = 32$ .