Problem C
Assignment Problem (Hard)

Note that this is a harder version of the problem assignmenteasy.

You, the Robot King, have to coordinate your robot employees $N=\{1,...,n\}$ by assigning them to different tasks $M=\{1,...m\}$. However, a robot can only be assigned to exactly one task; and being a cost-aware monarch, you have decided to minimize the robots’ total (aggregated) cost.

More formally, suppose $\mathbf{\text{c}}(i,j)\mapsto \mathbb{N}$ yields the cost for assigning robot $i\in N$ to task $j\in M$. Your goal, then, is to find an “assignment” (i.e., a bijection) $f:N\mapsto M$ that minimizes $\sum _{i\in N}c(i,f(i))$. In this problem, you may assume $m=n$ (so that $|N|=|M|$).

Input

In the first line there will be an integer $1\le n\le 1000$. Then, there will be $n$ lines, each with $n$ non-negative integers. The $j$th entry on the $i$th line corresponds to the cost for assigning robot $i$ to task $j$.

Output

First, there should be a line containing the total cost of an optimal assignment. Then, there should be one line representing an optimal assignment. The $i$th entry on this line should contain the task that the $i$th robot is assigned to. If there are more than one possible optimal assignments, any will do.

4
2 1 2 2
1 2 2 2
2 2 1 2
2 2 2 1

4
2 1 3 4

3
5 5 6
1 4 2
1 9 5

8
2 3 1