Optimal Enzyme Consumption

Professor W is studying a peculiar prokaryotic organism that grows only by consuming others of its kind. When two organisms encounter each other, the heavier one devours the lighter one (if their weights are equal, the outcome is arbitrary). Upon consuming, the victor’s weight becomes the sum of both weights, and the process consumes enzymes equal to that sum.

The professor has n organisms. He conducts k experiments. In each experiment he removes the m smallest organisms from his petri dish and arranges them in a circular tube in an arbitrary order of his choice. Then he initiates a process where every adjacent pair (neighbors in the circle) is provided with enzyme so they engage in combat. In each fight the heavier one consumes the lighter one, its weight becomes the sum of the two, and the enzyme used is equal to this sum. This merging (or fighting) is repeated until only one organism remains. The experiment’s enzyme cost is the total enzyme consumed during the merging process. The professor aims to minimize the enzyme consumption in each experiment. Note that by choosing an optimal circular arrangement, the merging process is equivalent to performing an optimal merge (as computed by the Huffman algorithm) on the set of m weights. The resulting organism (with weight equal to the sum of the merged organisms) is then placed back into the petri dish. After k experiments the dish will have fewer organisms. It is guaranteed that there will always be enough organisms to perform an experiment.

Your task is to compute the minimum total enzyme consumption after k experiments.

Note: The enzyme consumption when merging two organisms with weights \(a\) and \(b\) is \(a+b\). Each experiment merges the chosen m organisms into one (using an optimal merge strategy), and the cost for that experiment is the sum of the merge operations performed.

The overall total enzyme consumption is the sum of the enzyme consumed during each experiment.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) where \(n\) is the number of organisms, \(m\) is the number of organisms used in each experiment, and \(k\) is the number of experiments.

The second line contains \(n\) integers representing the weights of the organisms.

outputFormat

Output a single integer representing the minimum total enzyme consumption after performing k experiments optimally.

sample

5 2 1
3 1 2 4 5

3