Cleaning the Club Room!

Interview

Time limit1sMemory limit128 MB

Summary

Pick exactly M evenings to reset dirt to zero so the sum of daily visitors times dirt since the last cleaning is smallest.

Level: Medium5 of 10
Topics: Dynamic programming, Prefix sum
Solved: No attempts yet

Problem

Namgyu manages the club room. More people use it than before, the room has gotten dirty, and everyone who comes in feels discomfort.

The discomfort one person feels equals the dirtiness of the room on the morning of the day that person comes in. If the dirtiness is 3 on a day when 5 people come, all five feel discomfort 3, so the discomfort of that day adds up to 15. The dirtiness then grows by the number of people who came and left that day. In short, if the dirtiness on some morning is $d$ and $p$ people come and go that day, the discomfort of that day totals $d \times p$ , and after everyone leaves the dirtiness becomes $d + p$ .

Namgyu is lazy, so he cleans on exactly $M$ of the $N$ days. Cleaning always happens in the evening after everyone has left, and the dirtiness becomes 0 on the evening of a cleaning day. The dirtiness on the first morning is 0.

You know in advance how many people come and go on each of the $N$ days. Find the cleaning plan that makes the total discomfort as small as possible.

Input

The first line contains $N$ and $M$ . ( $1 \le N \le 100$ , $1 \le M \le \min(10, N)$ )

The second line contains the number of people who come and go on each day, $P_1, P_2, \ldots, P_N$ , separated by spaces. ( $1 \le P_i \le 20$ )

Output

On the first line, print the minimum possible total discomfort felt over the $N$ days.

On the second line, print the $M$ cleaning days that achieve that minimum, in increasing order, separated by single spaces. If several plans achieve the minimum, print the one whose increasing sequence of days is lexicographically smallest.

Hint

Over 8 days the numbers of people are $5, 8, 6, 10, 1, 15, 3, 9$ . Cleaning on the evenings of day 3 and day 6 gives these values.

Day	2	3	4	5	6	7	8
Dirtiness in the morning	5	13	0	10	11	0	3
Discomfort that day	40	78	0	10	165	0	27
Discomfort so far	40	118	118	128	293	293	320

Examples8

Example 1
Input
```
8 2
5 8 6 10 1 15 3 9
```
Expected output
```
320
3 6
```
Example 2
Input
```
1 1
7
```
Expected output
```
0
1
```
Example 3
Input
```
2 1
1 1
```
Expected output
```
0
1
```
Example 4
Input
```
6 2
1 1 1 1 1 1
```
Expected output
```
3
2 4
```
Example 5
Input
```
5 5
20 20 20 20 20
```
Expected output
```
0
1 2 3 4 5
```
Example 6
Input
```
5 1
1 1 1 1 20
```
Expected output
```
6
4
```
Example 7
Input
```
10 3
20 1 1 20 1 1 20 1 1 20
```
Expected output
```
122
2 4 7
```
Example 8
Input
```
3 2
20 20 20
```
Expected output
```
0
1 2
```