time limit per test: 1.25 sec. memory limit per test: 65536 KB
input: standard output: standard
Of course you know that some operating systems are not stable. Sasha learnt it only few days ago. Now there are very bad days of his life. He is an adminstrator of the network of n computers with different versions of such systems. Each computer is a workstation which is usually used to run a single program. But the programs often crash with a message "The system is busy or unstable" Sasha has determined some unsafety value corresponding to the frequency of program crash for each program on each workstation (the larger values correspond to more often crashes). Now he plans to arrange programs in such a way that the maximal unsafety value of all workstations will become minimal possible (because crashes slow down all the work!). Help him!
The first line of the input file contains the number of workstations n (1 ≤ n ≤ 500) which is equal to number of programs. The next n lines contain n numbers each — j-th number of i-th line contains the unsafety value for a program j on i-th computer. All numbers do not exceed 106 by their absolute values.
Write the maximal unsafety value on the first line. Then output n lines each corresponding to one program in format "i j" — i-th computer must run j-th program.
2 1 3 4 5
4 1 2 2 1
Andrew Stankevich, Andrew Lopatin
Petrozavodsk Summer Trainings 2003
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov