Fortune over Sportsmanship#12900

Fortune over Sportsmanship

2 seconds
256 megabytes
Hard

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

The marketing experts have devised an n \times n matrix , where P_{i, j} is the popularity score gained if player competes in a match with player . They also observed the following social phenomenon: whenever player competes against player and wins, player will inherit all the popularity scores of player , 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 to in descending order of their performance. In that sense, if players and were to compete in a match, where i < j, then player will always win.

Given the popularity matrix , 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.

Input

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

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

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

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

Examples

Example 1

Loading
Loading