Optimal Mars Keypad Layout

Mars phones have a similar keypad layout to Earth phones. Each phone has M numeric keys and you need to assign the N distinct Martian letters onto these keys. The letters assigned to any key must appear as a contiguous block.

When a letter is placed on a key, its input cost is determined by its position on that key. In particular, if a letter appears as the k^th letter on its key, then entering that letter requires k presses of the corresponding numeric key. For example, if on Earth phones the letter C is the 3rd letter on the key 2, then you need to press 2 three times to type C (and similarly for other letters).

In our problem, you are given M (the number of keys) and N (the number of distinct Martian letters). In addition, you are given the frequency of occurrence of each letter in a certain Martian text. You are allowed to choose any ordering of the letters and partition them into M contiguous groups (one group per key; some keys may remain unused if M > N). The cost to type a letter is the letter's frequency multiplied by its position index on its key. Your task is to design a layout that minimizes the total number of key presses needed to type the given text.

The total cost is computed as follows. Suppose after reordering the letters in descending order of frequency, letter i (with frequency f_i) is assigned to position j on its key. Then the overall cost is:

[ \text{Total Cost} = \sum_{\text{letter } i} f_i \times j_i. ]

The challenge is to partition the sorted frequency list into M contiguous segments (each segment corresponds to a key) so that the sum of the costs over all letters is minimized.

Input constraints and assumptions: It is guaranteed that all input values are positive integers. If M > N, you can assign at most one letter per key (i.e. some keys remain unused) leading to a minimal cost equal to the sum of frequencies.

Note: All formulas are written in \( \LaTeX \) format.

inputFormat

The first line of the input contains two integers M and N, representing the number of keys and the number of Martian letters respectively. The second line contains N integers, where the i^th integer represents the frequency of the i^th Martian letter.

Input Format:

M N
f1 f2 f3 ... fN

outputFormat

Output a single integer representing the minimum total key presses required to type the given Martian text.

sample

3 6
8 2 5 3 7 1

37