Description

There are $N$ single boys and $N$ single girls. The happiness of pairing boy $i$ with girl $j$ is $H_{i,j}$.

A matching is an arrangement of these $N$ boys and girls such that each boy has exactly one girlfriend and each girl has exactly one boyfriend.

The happiness of a matching is the sum of the happiness values of these $N$ pairs.

The classic task is to compute the maximum possible happiness, i.e., a maximum-weight perfect matching (also called an "assignment"). However, the maximum-weight perfect matching is not always unique. You need to compute the intersection of all maximum-weight perfect matchings.

Input Format

The first line contains a positive integer $N$.

Then follows an $N \times N$ matrix $H$, where $H_{i,j}$ denotes the happiness of pairing boy $i$ with girl $j$.

Output Format

On the first line, output the happiness of the maximum-weight perfect matching. Then output several lines, each containing a pair of integers $i$ and $j$, indicating that boy $i$ and girl $j$ appear in the intersection of all maximum-weight perfect matchings, in increasing order of $i$.

3
1 1 1
2 1 1
1 1 1

4
2 1

Hint

• For 30% of the testdata, $N \leq 30$.
• For 100% of the testdata, $1 \leq N \leq 80$, $0 \leq H_{i,j} \leq 5 \times 10^3$.

Translated by ChatGPT 5