0171. Unstable Systems

Input file name: unstable.in
Output file name: unstable.out
Time limit: 1 s
Memory limit: 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 106 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 ji-th computer must run j-th program.

Examples:

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


Source: Petrozavodsk Summer 2003. KOTEHOK's Contest, Sunday, August 31
Author: Andrew Lopatin

Discuss       Submit a solution



Printable version