/*
 * @(#) smt4.c - Program for solving distribution problem using Bradford
 * method (Task 4 (problem 802) at the Special Military Training course).
 * (c) 1998 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru
 * Freeware program source. All rights reserved.
 **
 * Language: ANSI C
 * Tested with: Watcom C compiler v11.0
 * Last modified: 1998-03-16 18:10:00 GMT+03:00
 */

#include <stdio.h> /* scanf(), printf() */

#define MAXN 20

int p[MAXN][MAXN],q[MAXN][MAXN];
int x[MAXN][MAXN];

void swap(int *a, int *b)
{
 int t=*a;
 *a=*b;
 *b=t;
}

void transp_matr(int a[MAXN][MAXN], int n, int m)
{
 int j;
 if (m>n)
  n=m;
 while (--n)
  for (j=n;j--;)
   swap(&a[n][j],&a[j][n]);
}

int sum_matr(int a[MAXN][MAXN], int x[MAXN][MAXN], int n, int m)
{
 int j,z=0;
 while (n--)
  for (j=m;j--;)
   if (x[n][j])
    z+=a[n][j];
 return z;
}

void input_matr(int a[MAXN][MAXN], int n, int m)
{
 int i,j;
 for (i=0;i<n;i++)
  for (j=0;j<m;j++)
   scanf("%d",&a[i][j]);
}

void print_vect(int b[MAXN], int m)
{
 int j;
 for (j=0;j<m;j++)
  printf(" %4d",b[j]);
 printf("\n");
}

void print_matr(int a[MAXN][MAXN], int n, int m)
{
 int i;
 for (i=0;i<n;i++)
  print_vect(a[i],m);
 printf("\n");
}

void print_nonzero(int x[MAXN][MAXN], int n, int m)
{
 int i,j;
 for (i=0;i<n;i++)
  for (j=0;j<m;j++)
   if (x[i][j])
    printf("X[%d,%d]=",i+1,j+1);
 printf("1\n\n");
}

void copy_matr(int a[MAXN][MAXN], int p[MAXN][MAXN], int n, int m)
{
 int j;
 while (n--)
  for (j=m;j--;)
   a[n][j]=p[n][j];
}

void clear_vect(int t[MAXN], int m)
{
 while (m--)
  t[m]=0;
}

int find_nonzero(int t[MAXN], int m)
{
 while (m-- && !t[m]);
 return m;
}

int find_max(int b[MAXN], int t[MAXN], int m)
{
 int j,k;
 for (k=0;k<m;k++)
  if (!t[k])
   break;
 for (j=k;++j<m;)
  if (!t[j] && b[k]<b[j])
   k=j;
 return k;
}

void mark_all_maxs(int a[MAXN][MAXN], int x[MAXN][MAXN], int n, int m)
{
 while (n--)
 {
  clear_vect(x[n],m);
  x[n][find_max(a[n],x[n],m)]=1;
 }
}

int check_one_border(int x[MAXN][MAXN], int n, int col)
{
 while (n && !x[--n][col]);
 while (n)
  if (x[--n][col])
   return 1;
 return 0;
}

int find_bad_border(int x[MAXN][MAXN], int n, int m)
{
 while (m--)
  if (check_one_border(x,n,m))
   break;
 return m;
}

int find_less_max(int a[MAXN][MAXN], int x[MAXN][MAXN], int t[MAXN],
                  int n, int m, int *col, int *oldcol)
{
 int j,k,row=-1;
 int val;
 while (n--)
  if (t[k=find_nonzero(x[n],m)] &&
      (a[n][k]-a[n][j=find_max(a[n],t,m)]<val || row<0))
  {
   row=n;
   *col=j;
   *oldcol=k;
   val=a[n][k]-a[n][j];
  }
 return row;
}

void dec_matr(int a[MAXN][MAXN], int t[MAXN], int n, int m, int delta)
{
 int i;
 while (m--)
  if (t[m])
   for (i=n;i--;)
    a[i][m]-=delta;
}

void iter_dec(int a[MAXN][MAXN], int x[MAXN][MAXN],
              int n, int m, int col)
{
 int oldcol,row;
 int t[MAXN];
 clear_vect(t,m);
 do
 {
  t[col]=1;
  row=find_less_max(a,x,t,n,m,&col,&oldcol);
  x[row][oldcol]=0;
  x[row][col]=1;
  dec_matr(a,t,n,m,a[row][oldcol]-a[row][col]);
 } while (check_one_border(x,n,col));
}

void find_cond_max(int a[MAXN][MAXN], int x[MAXN][MAXN], int n, int m)
{
 int col;
 mark_all_maxs(a,x,n,m);
 while ((col=find_bad_border(x,n,m))>=0)
  iter_dec(a,x,n,m,col);
}

int main(void)
{
 int n,m;
 scanf("%d%d",&n,&m);
 input_matr(p,n,m);
 copy_matr(q,p,n,m);
 if (n>m)
 {
  transp_matr(q,n,m);
  find_cond_max(q,x,m,n);
  transp_matr(x,m,n);
 }
  else find_cond_max(q,x,n,m);
 print_matr(p,n,m);
 print_nonzero(x,n,m);
 printf("Z=%d\n\n",sum_matr(p,x,n,m));
 return 0;
}