指派问题

【题目描述】

给定 $N \times N$ 的矩阵 $a_{ij}$。 求一个排列 $p_i$，使得 $\sum_{i = 0}^{N - 1} a_{ip_i}$ 最小。

若有多组解，输出其中任意一组。

【输入】

$N$
$a_{00}$ $a_{01}$ ... $a_{0,{N-1}}$
$a_{10}$ $a_{11}$ ... $a_{1,{N-1}}$
:
$a_{ {N-1}, 0 }$ $a_{ {N-1}, 1 }$ ... $a_{ {N-1}, {N-1} }$

【输出】

$X$
$p_0$ $p_1$ ... $p_{N-1}$

其中 $X = \sum_{i = 0}^{N - 1} a_{ip_i}$。

【输入样例】

3
4 3 5
3 5 9
4 1 4

【输出样例】

9
2 0 1

【数据范围】

• $1 \leq N \leq 500$
• $|a_{ij}| \leq 1000000000$

【来源】

Library Checker（yosupo06） assignment

本题为 special judge（输出任意合法解），暂不可本地评测。