Description

Suppose we want to arrange the window display of a flower shop in the most aesthetically pleasing way. There are $F$ bouquets of flowers, each of a different variety. At the same time, there are at least as many vases, arranged in a row in a fixed order, numbered sequentially from left to right as $1$ to $V$, where $V$ is the number of vases. Vase number $1$ is on the far left, and vase number $V$ is on the far right. The bouquets can be moved, and each bouquet is uniquely identified by an integer from $1$ to $F$. The integer identifying the bouquet determines the order in which the bouquets are placed in the vases—that is, if $i < j$, then bouquet $i$ must be placed in a vase to the left of bouquet $j$.

For example, suppose the azalea is identified by number $1$, the begonia by number $2$, and the carnation by number $3$. All bouquets must be placed in the vases in the order of their identifiers. That is, the azalea must be placed in a vase to the left of the begonia, and the begonia must be placed in a vase to the left of the carnation. If the number of vases is greater than the number of bouquets, the extra vases must remain empty, meaning each vase can hold at most one bouquet.

Each vase also differs in shape and color, so placing different bouquets in different vases will produce varying aesthetic effects, represented by an aesthetic value (an integer). The aesthetic value of an empty vase is $0$. In the example above, the aesthetic values of different vase-bouquet pairings can be represented in the following table.

According to the table, placing the azalea in vase $2$ would look very beautiful, but placing it in vase $4$ would look very unattractive.

To achieve the best aesthetic effect, the bouquets must be arranged to maximize the total aesthetic value while maintaining the order of the bouquets. If there are multiple arrangements with the maximum aesthetic value, any one of them can be output.

The problem data satisfies the following conditions:
$1 ≤ F ≤ 100$, where $F$ is the number of bouquets, numbered from $1$ to $F$.
$F ≤ V ≤ 100$, where $V$ is the number of vases.
$-50 ≤ A_{ij} ≤ 50$, where $A_{ij}$ is the aesthetic value of placing bouquet $i$ in vase $j$.

Input Format

The first line contains two numbers: $F$, $V$.
The subsequent $F$ lines each contain $V$ integers, where $A_{ij}$ is the $j$-th number in the $(i+1)$-th line of the input file.

Output Format

The first line is the aesthetic value produced by the program's arrangement.
The second line must contain $F$ numbers representing the arrangement, where the $K$-th number indicates the vase number in which bouquet $K$ is placed.

Vase 1   Vase 2   Vase 3   Vase 4   Vase 5  
Azalea   7        23       -5       -24      16  
Begonia  5        21       -4       10       23  
Carnation -21      5        -4       -20      20  

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

53 
2 4 5