410790: GYM104114 F Fortune over Sportsmanship

There is a tennis tournament happening right around the corner, with $$$n$$$ vicious participants.

The marketing experts have devised an $$$n \times n$$$ matrix $$$P$$$, where $$$P_{i, j}$$$ is the popularity score gained if player $$$i$$$ competes in a match with player $$$j$$$. They also observed the following social phenomenon: whenever player $$$i$$$ competes against player $$$j$$$ and wins, player $$$i$$$ will inherit all the popularity scores of player $$$j$$$, that is, $$$P_{i, x}$$$ becomes the maximum of $$$P_{i, x}$$$ and $$$P_{j, x}$$$, for all $$$1 \leq x \leq n$$$ (and similarly for $$$P_{x, i}$$$).

Since fairness isn't a concern, the tournament doesn't have to be perfect. In that sense, any set of $$$n-1$$$ matches played in order can be a valid tournament. To top if off, the contestants are numbered from $$$1$$$ to $$$n$$$ in descending order of their performance. In that sense, if players $$$i$$$ and $$$j$$$ were to compete in a match, where $$$i < j$$$, then player $$$i$$$ will always win.

Given the popularity matrix $$$P$$$, you have to decide the $$$n-1$$$ matches that are going to be played in order during the tournament, such that the total popularity score over the $$$n-1$$$ matches is as large as possible. Note that once a match takes place, the loser gets disqualified, therefore she/he cannot not participate in future matches.

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$), the number of players.

The $$$i$$$-th of the following $$$n$$$ lines contains $$$n$$$ integers $$$P_{i, 1}, P_{i, 2}, \ldots, P_{i, n}$$$, describing the $$$i$$$-th row of the popularity matrix $$$P$$$.

It is guaranteed that $$$1 \leq P_{i, j} \leq 10^6$$$ and $$$P_{i, j} = P_{j, i}$$$ for all $$$1 \leq i < j \leq n$$$. Moreover, $$$P_{i, i} = 0$$$ for all $$$1 \leq i \leq n$$$.

Output $$$n$$$ lines. The first line contains a single integer – the maximum possible total popularity score. Each of the following $$$n-1$$$ lines should contain two integers, indicating the participants that fight in each of the $$$n-1$$$ matches in order. If there are multiple solutions, output any of them.

5
0 2 3 4 5
2 0 4 5 6
3 4 0 6 7
4 5 6 0 8
5 6 7 8 0

26
4 5
3 4
2 3
2 1