一场网球锦标赛即将举行，有 $n$ 名竞争激烈的选手参加。

营销专家设计了一个 $n \times n$ 的矩阵 $P$，其中 $P_{i,j}$ 是选手 $i$ 与选手 $j$ 进行比赛时所能获得的人气值。他们还观察到了以下社会现象：每当选手 $i$ 与选手 $j$ 比赛并获胜时，选手 $i$ 将继承选手 $j$ 的所有人气值，也就是说，对于所有 $1 \le x \le n$，$P_{i,x}$ 将变为 $P_{i,x}$ 和 $P_{j,x}$ 的最大值（对于 $P_{x,i}$ 也是如此）。

由于不需要考虑公平性，锦标赛不需要是完美的。从这个意义上说，按顺序进行的任何 $n - 1$ 场比赛的集合都可以是一个有效的锦标赛。此外，参赛选手按其实力从强到弱依次编号为 $1$ 到 $n$。也就是说，如果选手 $i$ 和选手 $j$ 进行比赛，且 $i < j$，那么选手 $i$ 将总是获胜。

给定人气矩阵 $P$，你必须决定在锦标赛期间按顺序进行的 $n - 1$ 场比赛，使得这 $n - 1$ 场比赛的总人气值尽可能大。

请注意，一旦比赛进行，输掉的一方就会被淘汰，因此他/她不能参加未来的比赛。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 1000$)，表示选手的数量。

接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $P_{i,1}, P_{i,2}, \dots, P_{i,n}$，描述人气矩阵 $P$ 的第 $i$ 行。

保证对于所有 $1 \le i < j \le n$，有 $1 \le P_{i,j} \le 10^6$ 且 $P_{i,j} = P_{j,i}$。此外，对于所有 $1 \le i \le n$，有 $P_{i,i} = 0$。

输出格式

输出 $n$ 行。

第一行包含一个整数，表示最大可能得到的总人气值。

接下来的 $n - 1$ 行，每行应包含两个整数，按顺序表示在 $n - 1$ 场比赛中对决的选手。如果有多个解，输出其中任意一个。

样例

输入样例 1

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

输出样例 1

26
4 5
3 4
2 3
2 1