Number Beads

Interview

Time limit1sMemory limit128 MB

Summary

Split an ordered array into M contiguous groups to minimize the largest group sum, then output that value and the group sizes.

Level: Medium5 of 10
Topics: Binary search, Greedy, Prefix sum
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples1

Example 1
Input
```
8 3
5 4 2 6 9 3 8 7
```
Expected output
```
17
4 2 2
```