Mr. Road Runner bought a piece of land in the middle of a desert for a nominal amount. It turns out that the piece of land is now worth millions of dollars as it has an oil reserve under it. Mr. Road Runner contacts the ACME corp to set up the oil wells on his land. Setting up oil wells is a costly affair and the charges of setting up oil wells are as follows. 

The rectangular plot bought by Mr. Road Runner is divided into r * c blocks. Only some blocks are suitable for setting up the oil well and these blocks have been marked. ACME charges nothing for building the first oil well. For every subsequent oil well built, the cost would be the maximum ACME distance between the new oil well and the existing oil wells. 

If (x,y) is the position of the block where a new oil well is setup and (x1, y1) is the position of the block of an existing oil well, the ACME distance is given by 

max(|x-x1|, |y-y1|)

the maximum ACME distance is the maximum among all the ACME distance between existing oil wells and new wells. 

If the distance of any two adjacent blocks (horizontal or vertical) is considered 1 unit, what is the minimum cost (E) in units it takes to set up oil wells across all the marked blocks?

Input Format

The first line of the input contains two space separated integers r *c*. 

r lines follow each containing c space separated integers. 

1 indicates that the block is suitable for setting up an oil well, whereas 0 isn't. 

r c  
M11 M12 ... M1c  
M21 M22 ... M2c  
...  
Mr1 Mr2 ... Mrc  

Constraints
1 <= r, c <= 50

Output Format

Print the minimum value E as the answer. 

Sample Input
3 4
1 0 0 0
1 0 0 0
0 0 1 0

Sample Output
3  

Explanation

(1, 1) (2, 1) (3, 3) are the places where are to be setup. 

There are 3! = 6 ways to do it. 

(1, 1) (2, 1) (3, 3) ==> cost = 0 + 1 + 2 = 3 

(1, 1) (3, 3) (2, 1) ==> cost = 0 + 2 + 2 = 4 

(2, 1) (1, 1) (3, 3) ==> cost = 0 + 1 + 2 = 3 

(2, 1) (3, 3) (1, 1) ==> cost = 0 + 2 + 2 = 4 

(3, 3) (1, 1) (2, 1) ==> cost = 0 + 2 + 2 = 4 

(3, 3) (2, 1) (1, 1) ==> cost = 0 + 2 + 2 = 4  

So E = 3

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(r, c) = list(map(int, input().strip().split()))
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
res = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		res[i][j] = bs[j]
pre = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + res[i][j]
ab = res
bc = [[0] * n for i in range(n)]
res2 = [[0] * n for i in range(n)]
res3 = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = bc[i][j] = pre[I][J] - pre[i][J] - pre[I][j] + pre[i][j]
			res3[i][j] = min(res2[i][j] + d * (total - ab[i][j]), res2[i][j + 1] + d * (total - ab[i][j + 1]), res2[i + 1][j] + d * (total - ab[i + 1][j]), res2[i + 1][j + 1] + d * (total - ab[i + 1][j + 1]))
	(res2, res3) = (res3, res2)
	(ab, bc) = (bc, ab)
print(res2[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
res = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		res[i][j] = bs[j]
pre = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + res[i][j]
ab = res
bc = [[0] * n for i in range(n)]
res2 = [[0] * n for i in range(n)]
res3 = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = bc[i][j] = pre[I][J] - pre[i][J] - pre[I][j] + pre[i][j]
			res3[i][j] = min(res2[i][j] + d * (total - ab[i][j]), res2[i][j + 1] + d * (total - ab[i][j + 1]), res2[i + 1][j] + d * (total - ab[i + 1][j]), res2[i + 1][j + 1] + d * (total - ab[i + 1][j + 1]))
	(res2, res3) = (res3, res2)
	(ab, bc) = (bc, ab)
print(res2[0][0])


(r, c) = list(map(int, input().strip().split()))
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
res = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		res[i][j] = bs[j]
pre = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + res[i][j]
ab = res
bc = [[0] * n for i in range(n)]
res2 = [[0] * n for i in range(n)]
res3 = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = bc[i][j] = pre[I][J] - pre[i][J] - pre[I][j] + pre[i][j]
			res3[i][j] = min(res2[i][j] + d * (total - ab[i][j]), res2[i][j + 1] + d * (total - ab[i][j + 1]), res2[i + 1][j] + d * (total - ab[i + 1][j]), res2[i + 1][j + 1] + d * (total - ab[i + 1][j + 1]))
	(res2, res3) = (res3, res2)
	(ab, bc) = (bc, ab)
print(res2[0][0])


(r, c) = list(map(int, input().strip().split()))
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = list(map(int, input().strip().split()))
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = list(map(int, input().strip().split()))
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(k, s) = map(int, input().strip().split())
m = max(k, s)
r = [[0] * m for i in range(m)]
for i in range(k):
	bs = list(map(int, input().strip().split()))
	for j in range(s):
		r[i][j] = bs[j]
x = [[0] * (m + 1) for i in range(m + 1)]
for i in range(m):
	for j in range(m):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + r[i][j]
q = r
fz = [[0] * m for i in range(m)]
a = [[0] * m for i in range(m)]
anz = [[0] * m for i in range(m)]
for d in range(1, m):
	for i in range(m - d):
		I = i + d + 1
		for j in range(m - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(a[i][j] + d * (total - q[i][j]), a[i][j + 1] + d * (total - q[i][j + 1]), a[i + 1][j] + d * (total - q[i + 1][j]), a[i + 1][j + 1] + d * (total - q[i + 1][j + 1]))
	(a, anz) = (anz, a)
	(q, fz) = (fz, q)
print(a[0][0])


import math
import os
import random
import re
import sys
(o, c) = map(int, input().strip().split())
n = max(o, c)
f = [[0] * n for i in range(n)]
for i in range(o):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		f[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + f[i][j]
fs = f
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = list(map(int, input().strip().split()))
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(p, b) = map(int, input().strip().split())
n = max(p, b)
g = [[0] * n for i in range(n)]
for i in range(p):
	bs = list(map(int, input().strip().split()))
	for j in range(b):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
a = [[0] * n for i in range(n)]
t = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			t[i][j] = min(a[i][j] + d * (total - fs[i][j]), a[i][j + 1] + d * (total - fs[i][j + 1]), a[i + 1][j] + d * (total - fs[i + 1][j]), a[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(a, t) = (t, a)
	(fs, fz) = (fz, fs)
print(a[0][0])


import math
import os
import random
import re
import sys
(T, c) = map(int, input().strip().split())
n = max(T, c)
g = [[0] * n for i in range(n)]
for i in range(T):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(A, c) = map(int, input().strip().split())
U = max(A, c)
g = [[0] * U for P in range(U)]
for P in range(A):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[P][j] = bs[j]
x = [[0] * (U + 1) for i in range(U + 1)]
for P in range(U):
	for j in range(U):
		x[P + 1][j + 1] = x[P + 1][j] + x[P][j + 1] - x[P][j] + g[P][j]
fs = g
fz = [[0] * U for P in range(U)]
ans = [[0] * U for P in range(U)]
anz = [[0] * U for P in range(U)]
for d in range(1, U):
	for P in range(U - d):
		I = P + d + 1
		for j in range(U - d):
			J = j + d + 1
			total = fz[P][j] = x[I][J] - x[P][J] - x[I][j] + x[P][j]
			anz[P][j] = min(ans[P][j] + d * (total - fs[P][j]), ans[P][j + 1] + d * (total - fs[P][j + 1]), ans[P + 1][j] + d * (total - fs[P + 1][j]), ans[P + 1][j + 1] + d * (total - fs[P + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = list(map(int, input().strip().split()))
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


import math
import os
import random
import re
import sys
(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])


(r, c) = map(int, input().strip().split())
n = max(r, c)
g = [[0] * n for i in range(n)]
for i in range(r):
	bs = list(map(int, input().strip().split()))
	for j in range(c):
		g[i][j] = bs[j]
x = [[0] * (n + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(n):
		x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j]
fs = g
fz = [[0] * n for i in range(n)]
ans = [[0] * n for i in range(n)]
anz = [[0] * n for i in range(n)]
for d in range(1, n):
	for i in range(n - d):
		I = i + d + 1
		for j in range(n - d):
			J = j + d + 1
			total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j]
			anz[i][j] = min(ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d * (total - fs[i + 1][j + 1]))
	(ans, anz) = (anz, ans)
	(fs, fz) = (fz, fs)
print(ans[0][0])