0171. Unstable Systems

Имя входного файла:	unstable.in
Имя выходного файла:	unstable.out
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

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!

Input file

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 10⁶ by their absolute values.

Output file

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.

Examples:

unstable.in	unstable.out
2 1 3 4 5	4 1 2 2 1

Источник: Petrozavodsk Summer 2003. KOTEHOK's Contest, Sunday, August 31
Автор: Andrew Lopatin

Обсудить       Отправить решение



Версия для печати