Description

To input a letter, we must press its numeric key several times consecutively; the number of presses equals the letter’s position on that key. For example, in the scheme above, to input C, we press numeric key 2 three times; to input M, we press numeric key 6 once.

The Martian phone is similar to the Earth phone: it has $M$ Martian numeric keys, and you need to place the $N$ letters of the Martian alphabet onto these $M$ keys. (Likewise, the letters on any single numeric key must be a contiguous block of Martian letters.) Now, given the occurrence count of each letter in a passage of Martian text, your design must minimize the total number of key presses required to input this passage.

Input Format

The first line of input contains two numbers, $N$ and $M$, the number of Martian letters and the number of keys on the Martian phone, respectively. The next $N$ lines each contain one number, in order, giving the occurrence count of each letter in the passage. Each count does not exceed $1000$.

Output Format

The first line of output contains a single number, the minimum total number of key presses.

The next $M$ lines describe one design: each line contains a number, in order, indicating how many Martian letters are placed on each numeric key. (These numbers may be $0$.)

If multiple designs achieve the same minimum, output the one with the fewest letters on the first numeric key; if still tied, among those choose the one with the fewest letters on the second numeric key; and so on.

3 2
100
200
300

800
2
1

Hint

Constraints

For $100\%$ of the data, $1 \le N \le 500$, $1 \le M \le 100$.

Translated by ChatGPT 5