# 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.

Sample Input 1 | Sample Output 1 |
---|---|

4 2 1 2 2 1 2 2 2 2 2 1 2 2 2 2 1 |
4 2 1 3 4 |

Sample Input 2 | Sample Output 2 |
---|---|

3 5 5 6 1 4 2 1 9 5 |
8 2 3 1 |