cancer

Time limit: 2.5s Memory limit: 256MB Input: Output:

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 NN crabs, which he has ordered in some way from 11 to NN according to several characteristics, such as size, color, smell, etc. Furthermore, all crabs are at least a little aggressive, so each crab ii has aggressiveness AiA_{i}, where AiA_{i} is positive.

Darwin also owns KK 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 T1T_{1} crabs in the first aquarium, the next T2T_{2} crabs in the second one, and so on until the last TKT_{K} crabs - in the last aquarium. Obviously, T1+T2++TK=NT_{1} + T_{2} + \ldots + T_{K} = N and each TiT_{i} is a non-negative integer, but other than that the values of all TiT_{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 ii is afraid of all other crabs kept in the same aquarium as ii, and that amount of fear towards each such crab jj is equal to its aggressiveness AjA_{j}. Therefore, the total amount of fear crab ii feels is equal to the sum of all AjA_{j}, where jj are the other crabs kept in the same aquarium as ii.

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 KK 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 NN, KK and all AiA_{i}.

Input

From the first line of the standard input you should read two positive integers: NN and KK - the number of crabs and the number of aquariums. From the next line you should read NN positive integers: A1, A2,,ANA_{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

  • 1KN1051 \leq K \leq N \leq 10^{5}
  • 1Ai1071 \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)

  • N10N \leq 10

Subtask 2 (8 points)

  • N300N \leq 300

Subtask 3 (12 points)

  • N1 000N \leq 1 \ 000

Subtask 4 (24 points)

  • N6 000N \leq 6 \ 000

Subtask 5 (10 points)

  • N105N \leq 10^5
  • K=3K = 3

Subtask 6 (35 points)

  • N105N \leq 10^5

Example

stdin

8 4            
8 1 2 3 9 1 9 1

stdout

32

Explanation

There are 88 crabs that we have to keep in 44 aquariums. The optimal distribution is: crab 11 in aquarium 11; crabs 22, 33 and 44 in aquarium 22; crabs 55 and 66 in aquarium 33; crabs 77 and 88 in aquarium 44. Crab 11 feels no fear; crab 22 feels 55 fear; crab 33 feels 44 fear; crab 44 feels 33 fear; crab 55 feels 11 fear; crab 66 feels 99 fear; crab 77 feels 11 fear; crab 88 feels 99 fear. The total is 0+5+4+3+1+9+1+9=320 + 5 + 4 + 3 + 1 + 9 + 1 + 9 = 32.

stdin

6 3         
10 3 8 5 4 7

stdout

37

Log in or sign up to be able to send submissions!