Little Shop of Flowers

Interview

Time limit1sMemory limit128 MB

Summary

Place F ordered bunches into a row of V vases to maximize total aesthetic value, then output the lexicographically smallest optimal assignment.

Level: Medium6 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

You want to arrange the window of your flower shop as pleasantly as possible. You have $F$ bunches of flowers, each of a different kind, and a row of at least $F$ vases. The vases are fixed to the shelf and numbered $1$ through $V$ from left to right, so vase $1$ is the leftmost and vase $V$ is the rightmost. The bunches are movable and are identified by the integers $1$ through $F$ .

These id-numbers fix the required left-to-right order: whenever $i < j$ , bunch $i$ must stand in a vase to the left of the vase holding bunch $j$ . For example, with a bunch of azaleas (id $1$ ), begonias (id $2$ ), and carnations (id $3$ ), the azaleas must be left of the begonias, and the begonias must be left of the carnations. If there are more vases than bunches, the extra vases are left empty. Each vase holds at most one bunch.

Every vase has its own character, so placing a particular bunch in a particular vase yields an aesthetic value, given as an integer. Let $A_{i,j}$ be the aesthetic value of putting bunch $i$ into vase $j$ . Leaving a vase empty contributes $0$ .

For example, the aesthetic values might be:

	Vase 1	Vase 2	Vase 3	Vase 4	Vase 5
1 (Azaleas)	7	23	-5	-24	16
2 (Begonias)	5	21	-4	10	23
3 (Carnations)	-21	5	-4	-20	20

Here azaleas look great in vase 2 but awful in vase 4.

Place every bunch so that the required order is respected and the total aesthetic value is as large as possible.

Input

The first line contains two integers $F$ and $V$ .
Each of the next $F$ lines contains $V$ integers; the $j$ -th integer on the $(i+1)$ -th line is $A_{i,j}$ , the aesthetic value of placing bunch $i$ into vase $j$ .

Output

On the first line, print the maximum possible total aesthetic value.
On the second line, print $F$ integers: the $k$ -th integer is the vase that holds bunch $k$ in an arrangement achieving that maximum. If several arrangements reach the maximum, print the lexicographically smallest one — comparing the sequences of vase numbers for bunches $1, 2, \dots, F$ , the sequence that is smaller at the first position where they differ.

Constraints

$1 \le F \le 100$ , where $F$ is the number of bunches (numbered $1$ through $F$ ).
$F \le V \le 100$ , where $V$ is the number of vases.
$-50 \le A_{i,j} \le 50$ , where $A_{i,j}$ is the aesthetic value of putting bunch $i$ into vase $j$ .

Examples4

Example 1

Input

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

Expected output

53
2 4 5

Example 2
Input
```
1 1
5
```
Expected output
```
5
1
```
Example 3
Input
```
1 5
-3 -1 -1 -5 -2
```
Expected output
```
-1
2
```
Example 4
Input
```
2 2
1 2
3 4
```
Expected output
```
5
1 2
```