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 $\textbf{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 \leq n \leq 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