Flower Shop Window Arrangement

Problem Description

A flower shop has $F$ bouquets of flowers, each of a different variety. There are at least as many vases, arranged in a row in order. The positions of the vases are fixed, numbered from left to right as $1\sim V$, where $V$ is the number of vases.

The bouquets can be moved, and each bouquet is identified by an integer $1\sim F$. All bouquets must keep their identification order when placed into vases. For example, suppose the azalea has identification $1$, the begonia $2$, and the carnation $3$; then the azalea must be placed in a vase to the left of the begonia, and the begonia must be placed to the left of the carnation. Each vase can hold at most one bouquet.

The shape and color of each vase also differ, so placing different bouquets in different vases produces different aesthetic effects, represented by an aesthetic value (an integer $a_{i,j}$); the aesthetic value of an empty vase is $0$. In the example above, the aesthetic values of different combinations of vases and bouquets can be represented by the following table:

According to the table, an azalea placed in vase $2$ looks very nice, but placed in vase $4$ looks terrible.

To achieve the best aesthetic effect, the bouquets must be placed keeping their order, maximizing the total aesthetic value. If there is more than one arrangement achieving the maximum aesthetic value, output any one of them.

Input Format

The first line of the input file contains two integers $F$ and $V$, the number of bouquets and the number of vases, respectively.

Next is the matrix $a_{i,j}$, with $F$ rows, each containing $V$ integers; $a_{i,j}$ is the aesthetic value of placing bouquet $i$ in vase $j$.

Output Format

The first line of the output file is an integer: the maximum aesthetic value. The next line contains $F$ integers: the vase number where each bouquet is placed.

Sample Input 1

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

Sample Output 1

53
2 4 5

Constraints

For $100\%$ of the data, $1\le F\le V\le 100$.