Description

A flower shop currently has $F$ bouquets, each of a different kind. There are at least as many vases, arranged in a row in order. The positions of the vases are fixed and are 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 maintain the order of their identifiers when placed into vases. For example, suppose azalea has identifier $1$, begonia has identifier $2$, and carnation has identifier $3$; then 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. Each vase can hold only one bouquet.

Each vase has a unique shape and color, 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 above example, the aesthetic values of different pairings of vases and bouquets can be represented by the following table:

According to the table, placing the azalea in vase $2$ looks very good, but placing it in vase $4$ looks very bad.

To achieve the best aesthetic effect, under the constraint of preserving the bouquet order, the placement should maximize the total aesthetic value. Every bouquet must be placed into a vase. If there is more than one arrangement that attains the maximum aesthetic value, output any one of them.

Input Format

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

Then follows the matrix $a_{i,j}$ with $F$ rows and $V$ integers per row, where $a_{i,j}$ denotes the aesthetic value of placing bouquet $i$ into vase $j$.

Output Format

On the first line, output a single integer, the maximum total aesthetic value.
On the second line, output $F$ integers $p_1, p_2, \dots, p_F$, where $p_i$ is the index of the vase that holds bouquet $i$. All placed bouquets must satisfy: if $i < j$, then $p_i < p_j$.

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

53
2 4 5

Hint

• The order of bouquet identifiers must be strictly preserved.
• Constraints: For $100\%$ of the testdata, $1 \le F \le V \le 100$.
• Thanks to @Luo Kai for providing the SPJ.

Translated by ChatGPT 5