Number Beads

N number beads are arranged in a line in their fixed order on a rod. The beads cannot be removed from the rod, and their order cannot be changed.

Split the beads, preserving order, into M contiguous groups. Each group must contain at least one bead. For a split, compute the sum of the numbers in each group; among those sums, consider the maximum. The goal is to make that maximum as small as possible.

Write a program that outputs this minimum possible maximum group sum, and then the number of beads in each group from left to right.

The first line contains the number of beads N and the number of groups M. The second line contains the numbers written on the beads from left to right.

• 1 <= M <= N <= 300
• Each bead number is between 1 and 100, inclusive.

On the first line, output the minimum possible value of the maximum group sum. On the second line, output the number of beads in each group from left to right, separated by spaces.

If more than one optimal split exists, output any one of them.