Description

There are $n$ jobs to be assigned to $n$ people. When person $i$ does job $j$, the benefit is $c_{ij}$. Design an assignment that assigns $n$ jobs to $n$ people so that the total benefit is minimized or maximized.

Input Format

The first line contains one positive integer $n$, indicating there are $n$ jobs to be assigned to $n$ people. In the next $n$ lines, each line contains $n$ integers $c_{i,j}$, where $c_{i,j}$ is the benefit when person $i$ does job $j$.

Output Format

Output two lines: the minimum total benefit and the maximum total benefit, respectively.

5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1

5
14

Hint

$1 \leq n \leq 50, 0 \le c _ {i, j} \le 100$.

Each person can do only one job.

Translated by ChatGPT 5