Problem A
An Atypical Auction

This year, the auctioneer Amadeus has found some very impressive items to sell in his yearly auction. This year’s theme is “Original Algorithm Proofs”, and he has found big hits like Sharir’s linear time connected component algorithm, as well as some obscure Tarjan papers.

This year, the auction is in Algoland, where there are strict rules around auctions to keep them fair and accessible to everyone. There are two requirements for an Algoland auction:

• every participant has to bid on all items presented, and

• every participant can buy at most one item

This makes the auction ordering very important. To avoid people “gaming” the system, the auction order is hidden for the participants. In particular, the auction follows these exact steps:

1. All items are presented, in no particular order, on a website

2. An independent third-party corporation receives binding bids from every participant for every item

3. When all bids have been received, the auctioneer decides on an order in which the items are auctioned at (without knowing what the bids are)

4. The auctioneer receives information about items where is no winning bid, i.e. at least two participants have bid the highest amount. How they handle those cases is up to them.

This process went as usual until Amadeus picked the item order: Instead of telling Amadeus identical winning bids, the system informed Amadeus that every bid was unique, and printed them out for Amadeus to see. Clearly, this seems to be a debug setting they forgot to turn off, and Amadeus immediately reported the bug to the developers.

Even though the auction order is now fixed, Amadeus wonders if he could have gotten even higher prices if he knew this information before he picked the auction order.

Input

The first line contains two integers $N$ and $M$, the number of items and the number of participants, respectively. Then follows $N$ lines, each with $M$ integers.

The integer $c_{i,j}$ is the $j$th element on row $i$ and represents the bid participant $j$ offers on item $i$.

Output

Assuming Amadeus’ auction order is item $0$ then item $1, \ldots , N-1, N$, output the difference between the maximum possible income and the income provided by Amadeus’ auction order. Then, on the next line, output the optimal item order, separated by whitespace. If there are multiple possible answers, you may pick any of them.

Limits

• $0 < N \leq M \leq 300$

• $0 < c_{i,j} < 1\, 000\, 000$

• All $c_{i,j}$ are distinct

3 3
50 75 100
60 95 125
70 115 150

30
2 1 0

3 5
600 530 750 800 390
500 490 350 1200 310
1500 1250 1800 2000 1450

500
1 2 0

3 3
2 8 4
3 5 6
9 1 7

0
0 1 2