There are $N$ single boys and $N$ single girls. The happiness value of boy $i$ and girl $j$ being together is $H_{ij}$. A matching is an arrangement of these $N$ boys and $N$ girls such that each boy has exactly one girlfriend and each girl has exactly one boyfriend.

The happiness value of a matching is the sum of the happiness values of the $N$ boy-girl pairs. The classic problem is to calculate the matching with the maximum happiness value, which is the perfect matching. However, a perfect matching is not always unique. You need to calculate, for all perfect matchings, what their intersection is.

Input

The first line contains an integer $N$. The following is an $N \times N$ matrix $H$, where $H_{ij}$ represents the happiness value of boy $i$ and girl $j$ being together. ($0 \le H_{ij} \le 5000$)

Output

The first line outputs the maximum happiness value of a perfect matching. The following lines contain several pairs, each line being an integer $i$ and $j$, representing that boy $i$ and girl $j$ are in the intersection of all perfect matchings. Output in increasing order of $i$.

Examples

Input 1

3
1 1 1
2 1 1
1 1 1

Output 1

4
2 1

Constraints

For 30% of the data, $N \le 30$ For 100% of the data, $N \le 80$