Poor Windprayer. This time a terrible hurricane has seriously damaged the roof of his house. Now he wants to repair it with minimum cost.
You can consider the roof as a N by M rectangle, each grid is associated with a damage value, indicating the degree of damage of that grid (a grid is all right and shouldn't to be repaired if the damage value is 0).
Only 1*2 and 2*1 woods are available to repair the roof, and for some visual reason Windprayer will buy woods of same spec and same price. A piece of wood can be used to repair the roof if the price of it is not less than the sum of damage value of the two grids it covers.
Input:
The input file contain several test cases, each test case begin with two integers N and M (2 <= N, M <= 50), which is size of the roof. N lines follow, each with M non-negative integer not greater than 10000000, showing the damage value.
Output:
For each test case, if it's impossible to repair the roof, output "pat", otherwise, output the minimum cost in the first line, then in each of the following lines, output "(X1,Y1) (X2,Y2)", where (X1, Y1) and (X2, Y2) are positions that piece of wood will cover.
Sample input:
2 2
1 2
3 4
2 2
0 1
1 1
Sample output:
12
(0,1) (1,1)
(1,0) (0,0)
pat
