#include <iostream>#include <queue>#include <vector>using namespace std;#include <cstdio>#include <cstring>#define MAXN 1500#define N 55#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)int hungary(int m,int n,int mat[][MAXN],int* match1,int* match2){int s[MAXN],t[MAXN],p,q,ret=0,i,j,k,r;vector<int> e[MAXN];for(i=0;i<m;++i)for(j=0;j<n;++j)if (mat[i][j]) e[i].push_back(j);for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)for(r=0,k=s[p];r<e[k].size()&&match1[i]<0;++r)if (t[j=e[k][r]]<0){s[++q]=match2[j],t[j]=k;if (s[q]<0)for (p=j;p>=0;j=p)match2[j]=k=t[j],p=match1[k],match1[k]=j;}return ret;}int n, m, num;int mat[MAXN][MAXN], mx[MAXN], my[MAXN];int x[2][MAXN], y[2][MAXN], ny, nx;int g[N][N], f[N][N];int move[2][4] = {{0, 0, 1, -1}, {1, -1, 0, 0}};void init() { nx = ny = 0; memset(f, -1, sizeof f); memset(mat, 0, sizeof mat); for(int i = 0; i != n; ++i) { for(int j = 0; j != m; ++j) { if(f[i][j] != -1 || !g[i][j]) continue; queue<pair<int,int> > q; q.push(make_pair(i, j)); f[i][j] = 0; while(q.size()) { pair<int, int> t = q.front(); q.pop(); if(f[t.first][t.second]) { y[0][ny] = t.first; y[1][ny ++] = t.second; } else { x[0][nx] = t.first; x[1][nx ++] = t.second; } for(int i = 0; i != 4; ++i) { int x = t.first + move[0][i], y = t.second + move[1][i]; if(x >= 0 && x < n && y >= 0 && y < m && f[x][y] == -1 && g[x][y] != 0) { f[x][y] = f[t.first][t.second] ^ 1; q.push(make_pair(x, y)); } } } } }}bool input() { int i, j; if(scanf("%d%d", &n, &m) == -1) return false; for(num = i = 0; i != n; ++i) for(j = 0; j != m; ++j) { scanf("%d", &g[i][j]); if(g[i][j] != 0) ++ num; } init(); return true;}void gen(int cost) { for(int i = 0; i != nx; ++i) { int ix = x[0][i], iy = x[1][i]; for(int j = 0; j != ny; ++j) { int jx = y[0][j], jy = y[1][j]; if(ix == jx && (jy - iy == 1 || iy - jy == 1) || iy == jy && (ix - jx == 1 || jx - ix == 1)) { if(g[ix][iy] + g[jx][jy] <= cost) mat[i][j] = 1; else mat[i][j] = 0; } } }}void solve() { gen(20000000); if((num & 1) || (hungary(nx, ny, mat, mx, my) != num / 2)) { puts("pat"); return; }; if(num == 0) { puts("0"); return; } int l = 0, r = 20000000; while(l < r) { int mid = (l + r) / 2; gen(mid); if(hungary(nx, ny, mat, mx, my) == num / 2) r = mid; else l = mid + 1; } gen(r); int t = hungary(nx, ny, mat, mx, my); if(t != num / 2) puts("pat"); else { cout << r * (long long)num / 2 << endl; for(int i = 0; i != nx; ++i) printf("(%d,%d) (%d,%d)n", x[0][i], x[1][i], y[0][mx[i]], y[1][mx[i]]); }}int main() { while(input()) solve(); return 0;}
