Optimal Vase Arrangement

A flower shop has \(F\) bouquets, each of a different kind, and at least as many vases arranged in a row with fixed positions numbered from \(1\) to \(V\). Each bouquet is identified by an integer from \(1\) to \(F\) and must be placed in one of the vases while preserving the order of the bouquet identifiers (i.e. bouquet 1 must be to the left of bouquet 2, and so on). Each vase can hold at most one bouquet.

Placing bouquet \(i\) in vase \(j\) yields an aesthetic value of \(a_{i,j}\), while an empty vase has an aesthetic value of 0. Different combinations produce different overall aesthetics, and the goal is to choose vases for all bouquets (maintaining the order) so that the total aesthetic value is maximized. If there are multiple optimal arrangements, output any one of them.

Input Format: The first line consists of two integers \(F\) and \(V\) \((1 \le F \le V \le 100)\). The next \(F\) lines each contain \(V\) integers, where the \(j\)th number on the \(i\)th line represents \(a_{i,j}\).

Output Format: The first line should contain the maximum total aesthetic value. The second line should contain \(F\) integers indicating the selected vase positions (in increasing order) for bouquets \(1\) to \(F\), separated by spaces.

inputFormat

The input begins with two space-separated integers (F) and (V), where (F) is the number of bouquets and (V) is the number of vases. This is followed by (F) lines; each line contains (V) integers representing the aesthetic values (a_{i,1}, a_{i,2}, \ldots, a_{i,V}) for placing the (i)th bouquet in each vase.

outputFormat

The output consists of two lines. The first line prints the maximum total aesthetic value achievable. The second line prints (F) integers separated by spaces, where the (i)th integer denotes the vase number chosen for the (i)th bouquet.

sample

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

53
2 4 5