Problem:
 Score : 500 points    Problem Statement We have a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i -th row from the top and the j -th column from the left.  The square (i, j) has two numbers A_{ij} and B_{ij} written on it.  First, for each square, Takahashi paints one of the written numbers red and the other blue.  Then, he travels from the square (1, 1) to the square (H, W) . In one move, he can move from a square (i, j) to the square (i+1, j) or the square (i, j+1) . He must not leave the grid.  Let the unbalancedness be the absolute difference of the sum of red numbers and the sum of blue numbers written on the squares along Takahashi's path, including the squares (1, 1) and (H, W) .  Takahashi wants to make the unbalancedness as small as possible by appropriately painting the grid and traveling on it.  Find the minimum unbalancedness possible.      Constraints  2 \leq H \leq 80  2 \leq W \leq 80  0 \leq A_{ij} \leq 80  0 \leq B_{ij} \leq 80  All values in input are integers.         Input Input is given from Standard Input in the following format:  H  W  A_{11}  A_{12}  \ldots  A_{1W}  :  A_{H1}  A_{H2}  \ldots  A_{HW}  B_{11}  B_{12}  \ldots  B_{1W}  :  B_{H1}  B_{H2}  \ldots  B_{HW}       Output Print the minimum unbalancedness possible.        Sample Input 1 2 2
1 2
3 4
3 4
2 1      Sample Output 1 0  By painting the grid and traveling on it as shown in the figure below, the sum of red numbers and the sum of blue numbers are 3+3+1=7 and 1+2+4=7 , respectively, for the unbalancedness of 0 .        Sample Input 2 2 3
1 10 80
80 10 1
1 2 3
4 5 6      Sample Output 2 2

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*80+2
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        else:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

h,w = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [list(map(int, input().split())) for i in range(h)]
ma = 80*2*80
DP = [[[0]*ma for i in range(w)] for i in range(h)]

for i in range(h):
    for j in range(w):
        k = abs(a[i][j]-b[i][j])
        if i==0 and j==0:
            DP[i][j][k] = 1
            continue
        elif i == 0:
            up = min((i+j+1)*80+1, ma-k)
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k]
        elif j == 0:
            for l in range(up):
                DP[i][j][l] = DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
        else:
            for l in range(up):
                DP[i][j][l] = DP[i][j-1][abs(l-k)] | DP[i][j-1][l+k] | DP[i-1][j][abs(l-k)] | DP[i-1][j][l+k]
for i in range(ma):
    if DP[-1][-1][i]:
        print(i)
        exit()

Solution (Python):
def main():
    h,w=map(int,input().split())
    L=80*(h+w)+1
    a=[list(map(int,input().split())) for i in range(h)]
    b=[list(map(int,input().split())) for i in range(h)]


    x=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    

    L=12800
    
    state=[[0]*w for _ in range(h)]
    delta=x[0][0]
    state[0][0]=(2**L>>delta)|(2**L<<delta)

    for j in range(1,w):
        delta=x[0][j]
        state[0][j]=(state[0][j-1]>>delta)|(state[0][j-1]<<delta)

    for i in range(1,h):
        delta=x[i][0]
        state[i][0]=(state[i-1][0]>>delta)|(state[i-1][0]<<delta)

    for i in range(1,h):
        for j in range(1,w):
            delta=x[i][j]
            state[i][j]=(state[i][j-1]>>delta)|(state[i][j-1]<<delta)
            state[i][j]|=(state[i-1][j]>>delta)|(state[i-1][j]<<delta)

    
    ans = 10**9
    for i in range(L*2):
        if state[h-1][w-1] & 1:
            ans = min(ans,abs(i-L))
        state[h-1][w-1]>>=1
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.buffer.readline







def main():
	h,w=map(int,input().split())
	A=[list(map(int,input().split())) for _ in range(h)]
	B=[list(map(int,input().split())) for _ in range(h)]
	C=[[0]*w for _ in range(h)]
	for i in range(h):
		for j in range(w):
			C[i][j]=abs(A[i][j]-B[i][j])
	D=[[0]*w for _ in range(h)]
	D[0][0]=(1<<C[0][0]+5000)|(1>>C[0][0]+5000)
	for i in range(h):
		for j in range(w):
			if i>0:
				D[i][j]=D[i][j]|(D[i-1][j]<<C[i][j])|(D[i-1][j]>>C[i][j])
			if j>0:
				D[i][j] = D[i][j]|(D[i][j-1] << C[i][j]) | (D[i][j-1] >> C[i][j])

	val=D[-1][-1]
	ans=5000

	for i in range(10000):
		if val>>i&1:
			ans=min(ans,abs(i-5000))
	print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
la = [list(map(int,input().split())) for i in range(h)]
for i in range(h):
    l = list(map(int,input().split()))
    for j,num in enumerate(l):
        la[i][j] = abs(la[i][j]-num)
dp = [[0 for i in range(w)] for j in range(h)]
k = (h+w)*80+2
dp[0][0] = 1 << (k+la[0][0]) | 1 << (k-la[0][0])

for i in range(h):
    for j in range(w):
        if i:
            dp[i][j] |= (dp[i-1][j] << la[i][j]) | dp[i-1][j] >> la[i][j]
        if j:
            dp[i][j] |= (dp[i][j-1] << la[i][j]) | dp[i][j-1] >> la[i][j]

check = dp[-1][-1]       
for i in range(k):
    if (check >> k+i) & 1 or (check >> k-i) & 1:
        print(i)
        exit()

Solution (Python):
import sys

input = sys.stdin.buffer.readline







def main():
	h,w=map(int,input().split())
	A=[list(map(int,input().split())) for _ in range(h)]
	B=[list(map(int,input().split())) for _ in range(h)]
	C=[[0]*w for _ in range(h)]
	for i in range(h):
		for j in range(w):
			C[i][j]=abs(A[i][j]-B[i][j])
	D=[[0]*w for _ in range(h)]
	D[0][0]=(1<<C[0][0]+5000)|(1>>C[0][0]+5000)
	for i in range(h):
		for j in range(w):
			if i>0:
				D[i][j]=D[i][j]|(D[i-1][j]<<C[i][j])|(D[i-1][j]>>C[i][j])
			if j>0:
				D[i][j] = D[i][j]|(D[i][j-1] << C[i][j]) | (D[i][j-1] >> C[i][j])

	val=D[-1][-1]
	ans=5000

	for i in range(10000):
		if val>>i&1:
			ans=min(ans,abs(i-5000))
	print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
la = [list(map(int,input().split())) for i in range(h)]
for i in range(h):
    l = list(map(int,input().split()))
    for j,num in enumerate(l):
        la[i][j] = abs(la[i][j]-num)
dp = [[0 for i in range(w)] for j in range(h)]
k = (h+w)*80+2
dp[0][0] = 1 << (k+la[0][0]) | 1 << (k-la[0][0])

for i in range(h):
    for j in range(w):
        if i:
            dp[i][j] |= (dp[i-1][j] << la[i][j]) | dp[i-1][j] >> la[i][j]
        if j:
            dp[i][j] |= (dp[i][j-1] << la[i][j]) | dp[i][j-1] >> la[i][j]
        
s = bin(dp[-1][-1])[2:]
l = len(s)-1
ans = float('inf')
for i in range(l,-1,-1):
  if s[i]=='1':
    m = abs(l-i-k)
    if m<ans:
      ans = m
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
la = [list(map(int,input().split())) for i in range(h)]
for i in range(h):
    l = list(map(int,input().split()))
    for j,num in enumerate(l):
        la[i][j] = abs(la[i][j]-num)
dp = [[0 for i in range(w)] for j in range(h)]
k = (h+w)*80+2
dp[0][0] = 1 << (k+la[0][0]) | 1 << (k-la[0][0])

for i in range(h):
    for j in range(w):
        if i:
            dp[i][j] |= (dp[i-1][j] << la[i][j]) | dp[i-1][j] >> la[i][j]
        if j:
            dp[i][j] |= (dp[i][j-1] << la[i][j]) | dp[i][j-1] >> la[i][j]
        
s = bin(dp[-1][-1])[2:]
l = len(s)-1
ans = float('inf')
for i in range(l,-1,-1):
  if s[i]=='1':
    m = abs(l-i-k)
    if m<ans:
      ans = m
print(ans)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    H,W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

    M = 160*80
    dp = [[0 for _ in range(W)] for __ in range(H)]
    dp[0][0] = 1 << (C[0][0] + M)
    for i in range(H):
        for j in range(W):
            for ni,nj in [(i,j+1),(i+1,j)]:
                if ni >= H or nj >= W: continue
                t = C[ni][nj]
                dp[ni][nj] |= dp[i][j] << t
                dp[ni][nj] |= dp[i][j] >> t
    
    a = dp[H-1][W-1]
    ans = 0
    while True:
        if a & (1 << (M+ans)) or a & (1 >> (M-ans)): break
        ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
h, w= map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
B = [list(map(int, input().split())) for _ in range(h)]

C = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

import numpy as np
d = 80*(h+w-1)
D = 2*d+1
dp = [[0]*w for j in range(h)]
dp[0][0] = np.zeros(D, np.bool)
dp[0][0][d+C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        x = np.zeros(D, np.bool)
        if i != 0:
            x[C[i][j]:] |= dp[i-1][j][:D-C[i][j]]
            x[:D-C[i][j]] |= dp[i-1][j][C[i][j]:]
        if j != 0:
            x[C[i][j]:] |= dp[i][j-1][:D-C[i][j]]
            x[:D-C[i][j]] |= dp[i][j-1][C[i][j]:]
        dp[i][j] = x

temp = np.where(dp[-1][-1]>0)[0] - d
temp = abs(temp)
print(min(temp))

Solution (Python):
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

M = (H+W)*80
dp = [[0] * W for _ in range(H)]
dp[0][0] |= 1 << M
for i in range(H):
    for j in range(W):
        bit = dp[i][j]
        if i > 0:
            bit |= dp[i-1][j]
        if j > 0:
            bit |= dp[i][j-1]
        dp[i][j] = (bit >> C[i][j]) | (bit << C[i][j])
ans = M
for i in range(M*2):
    if (dp[-1][-1] >> i) & 1:
        ans = min(ans, abs(M-i))
print(ans)

Solution (Python):
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

M = (H+W)*80
dp = [[0] * W for _ in range(H)]
dp[0][0] |= 1 << (M-C[0][0])
for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        bit = 0
        if i > 0:
            bit |= dp[i-1][j]
        if j > 0:
            bit |= dp[i][j-1]
        dp[i][j] = (bit >> C[i][j]) | (bit << C[i][j])
ans = M
for i in range(M+1):
    if (dp[-1][-1] >> i) & 1:
        ans = min(ans, abs(M-i))
print(ans)

Solution (Python):
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
d=[[a[i][j]-b[i][j]for j in range(w)]for i in range(h)]
dp=[w*[0]for _ in range(h)]
dp[0][0]=1<<(80+d[0][0])|1<<(80-d[0][0])
for i in range(h):
  for j in range(w):
    if i!=0:
      dp[i][j]|=(dp[i-1][j]<<80+d[i][j])
      dp[i][j]|=(dp[i-1][j]<<80-d[i][j])
    if j!=0:
      dp[i][j]|=(dp[i][j-1]<<80+d[i][j])
      dp[i][j]|=(dp[i][j-1]<<80-d[i][j])
n=dp[-1][-1]|(1<<15000)
ans=1<<1000
for i in range(15000):
  if n&(1<<i):ans=min(ans,abs(i-(h+w-1)*80))
print(ans)

Solution (Python):
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
d=[[a[i][j]-b[i][j]for j in range(w)]for i in range(h)]
dp=[w*[0]for _ in range(h)]
dp[0][0]=1<<(80+d[0][0])|1<<(80-d[0][0])
for i in range(h):
  for j in range(w):
    if i!=0:
      dp[i][j]|=(dp[i-1][j]<<80+d[i][j])
      dp[i][j]|=(dp[i-1][j]<<80-d[i][j])
    if j!=0:
      dp[i][j]|=(dp[i][j-1]<<80+d[i][j])
      dp[i][j]|=(dp[i][j-1]<<80-d[i][j])
n=dp[-1][-1]|(1<<15000)
ans=1<<1000
for i in range(15000):
  if n&(1<<i):ans=min(ans,abs(i-(h+w-1)*80))
print(ans)

Solution (Python):
import math

h, w = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
b = [list(map(int,input().split())) for i in range(h)]

diff = [[abs(x-y) for x,y in zip(ar,br)] for ar,br in zip (a,b)]

M = 80*(h+w)
dp = [[0 for j in range(w)] for i in range(h)]
dp[0][0] = 1<<(diff[0][0]+M)
for i in range(h):
    for j in range(w):
        if i > 0:
            dp[i][j] |= (dp[i-1][j]<<diff[i][j])|(dp[i-1][j]>>diff[i][j])
        if j > 0:
            dp[i][j] |= (dp[i][j-1]<<diff[i][j])|(dp[i][j-1]>>diff[i][j])
        dp[i][j] &= (1<<(M*2))-1
for k in range(M):
    if (dp[h-1][w-1]>>(k+M))&1 == 1:
        print(k)
        break

Solution (Python):
def fold(x,m):
    y = 0
    for _ in range(m):
        y |= x&1
        y <<= 1
        x >>= 1
    return x|y

lmi = lambda: list(map(int, input().split()))

h,w = lmi()
a = [lmi() for _ in range(2*h)]
g = [[abs(a[i][j] - a[i+h][j]) for j in range(w)] for i in range(h)]
m = 12801
mask = (1<<m) - 1

a = [0]*(w+1)
a[0] = 1
for i in range(h):
  for j in range(w):
    cur,par = g[i][j], a[j]|a[j-1]
    a[j] = par<<cur&mask|fold(par,cur)
v = a[-2]
print((v&-v).bit_length() - 1)

Solution (Python):

h,w = map(int, input().split( ))
a = []
for i in range(h):
    ai = list(map(int, input().split( )))
    a.append(ai)
for i in range(h):
    bi = list(map(int, input().split( )))
    for j in range(w):
        a[i][j]-=bi[j]
        a[i][j] = abs(a[i][j])


dp = [[0 for j in range(w)] for i in range(h)]
a2 = [a[i][j] for i in range(h) for j in range(w)]
mxa = max(a2)


tmp=1<<mxa*(h+w)+10

dp[0][0]|=tmp<<a[0][0]
dp[0][0]|=tmp>>a[0][0]

for j in range(1,w):
    dp[0][j]=dp[0][j-1]<<a[0][j]
    dp[0][j]|=dp[0][j-1]>>a[0][j]

for i in range(1,h):
    for j in range(w):
        dp[i][j]=dp[i-1][j]<<a[i][j]
        dp[i][j]|=dp[i-1][j]>>a[i][j]
        if j:
            dp[i][j]|=dp[i][j-1]<<a[i][j]
            dp[i][j]|=dp[i][j-1]>>a[i][j]

tmp1 = dp[h-1][w-1]

tmp1>>=mxa*(h+w)+10


for k in range(mxa*(h+w)+10):
    if tmp1&1:
        print(k)
        exit()
    tmp1>>=1

Solution (Python):
import numpy as np
import itertools

H,W=map(int,input().split())
A=[list(map(int, input().split())) for _ in range(H*2)]
M=[[abs(A[i][j]-A[H+i][j]) for j in range(W)] for i in range(H)]
m=max(max(j for j in i) for i in M)
r=m*(H+W)+1
dp=np.zeros((H,W,r),dtype='bool')
dp[0][0][M[0][0]]=True
it = itertools.product(range(H),range(W))
next(it)
for h,w in it:
    m=M[h][w]
    dp[h][w][m:] |= dp[h][w-1][:r-m] | dp[h-1][w][:r-m]
    dp[h][w][:r-m] |= dp[h][w-1][m:] | dp[h-1][w][m:]
    dp[h][w][:m] |= dp[h][w-1][m:0:-1] | dp[h-1][w][m:0:-1]

for i in range(r):
    if dp[-1][-1][i]:
        print(i)
        break

Solution (Python):
def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    C = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            C[h][w] = abs(A[h][w] - B[h][w])

    dp = [[0 for _ in range(6400)] for _ in range(H*W)]
    dp[0][C[0][0]] = 1

    for d in range(H*W):
        h, w = divmod(d, W)
        for k in range(6400):
            if not dp[h*W+w][k]:
                continue
            nh, nw = h+1, w+1
            if nh < H:
                if k + C[nh][w] < 6400:
                    dp[nh*W+w][k+C[nh][w]] = 1
                dp[nh*W+w][abs(k-C[nh][w])] = 1
            if nw < W:
                if k + C[h][nw] < 6400:
                    dp[h*W+nw][k+C[h][nw]] = 1
                dp[h*W+nw][abs(k-C[h][nw])] = 1

    for k in range(6400):
        if dp[-1][k]:
            print(k)
            exit()

if __name__ == "__main__":
    main()

Solution (Python):
h, w = map(int, input().split())
ab = []
for i in range(h * 2):
    ab.extend(list(map(int, input().split())))

abs_table = [[0] * w for _ in range(h)]
dp = [[0] * w for _ in range(h)]

s = h * w
i = 0
j = 0
for k in range(s):
    if w == j:
        j = 0
        i += 1
    a, b = ab[k], ab[k+s]
    abs_table[i][j] = abs(a - b)
    j += 1
   
n = abs_table[0][0]  
dp[0][0] = 2**(n * 2)  | 1
    
for i in range(h):
    for j in range(w):
        a = abs_table[i][j]
        u = 0
        l = 0
        if i:
            u = dp[i-1][j]
            u = u << a * 2 | u | u
        if j:
            l = dp[i][j-1]
            l = l << a * 2 | l | l
            
        if not u and not l:
            pass
        elif not l:
            dp[i][j] = u
        elif not u:
            dp[i][j] = l
        else:
            len_u = len(bin(u)[2:])
            len_l = len(bin(l)[2:])
            delta = len_u - len_l
            if delta == 0:
                dp[i][j] = u | l
            elif delta < 0:
                dp[i][j] = u << abs(delta) // 2 | l
            else:
                dp[i][j] = u | l << delta // 2

flag = bin(dp[-1][-1])[2:]
zero = len(flag) // 2
for i, v in enumerate(flag[zero:]):
    if v == '1':
        print(i)
        break

Solution (Python):
def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = [[set() for j in range(W)] for i in range(H)]
    dp[0][0].add(X[0][0])
    dp[0][0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            if h > 0:
                for d in dp[h - 1][w]:
                    s.add(d + x)
                    s.add(abs(d - x))

            if w > 0:
                for d in dp[h][w - 1]:
                    s.add(d + x)
                    s.add(abs(d - x))

            dp[h][w] = s

    ans = min([abs(s) for s in dp[H - 1][W - 1]])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
h,w=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(2*h)]
board=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    board[i][j]+=arr[i][j]
for i in range(h):
  for j in range(w):
    board[i][j]=abs(board[i][j]-arr[h+i][j])
dp=[[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(board[0][0])
for i in range(h):
  for j in range(w):
    if i!=0:
      for k in dp[i-1][j]:
        dp[i][j].add((k+board[i][j])%640)
        dp[i][j].add(abs(k-board[i][j])%640)
    if j!=0:
      for k in dp[i][j-1]:
        dp[i][j].add((k+board[i][j])%640)
        dp[i][j].add(abs(k-board[i][j])%640)
print(min(dp[h-1][w-1]))

Solution (Python):
h,w=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(2*h)]
board=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    board[i][j]+=arr[i][j]
for i in range(h):
  for j in range(w):
    board[i][j]=abs(board[i][j]-arr[h+i][j])
dp=[[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(board[0][0])
for i in range(h):
  for j in range(w):
    if i!=0:
      for k in dp[i-1][j]:
        dp[i][j].add((k+board[i][j])%800)
        dp[i][j].add(abs(k-board[i][j])%800)
    if j!=0:
      for k in dp[i][j-1]:
        dp[i][j].add((k+board[i][j])%800)
        dp[i][j].add(abs(k-board[i][j])%800)
print(min(dp[h-1][w-1]))

Solution (Python):
H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
B = [list(map(int,input().split())) for _ in range(H)]

C = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])

dp = [[0 for k in range(6400)] for g in range(H*W)]
dp[0][C[0][0]] = 1

for g in range(H*W):
    i,j = divmod(g,W)
    for k in range(6400):
        if not dp[i*W+j][k]:
            continue
        ni,nj = i+1,j+1
        if ni < H:
            if k+C[ni][j]<6400:
                dp[ni*W+j][k+C[ni][j]] = 1
            dp[ni*W+j][abs(k-C[ni][j])] = 1
        if nj < W:
            if k+C[i][nj]<6400:
                dp[i*W+nj][k+C[i][nj]] = 1
            dp[i*W+nj][abs(k-C[i][nj])] = 1

for k in range(6400):
    if dp[-1][k]:
        print(k)
        break

Solution (Python):
def main():

    H,W = map(int,input().split())
    A = [list(map(int,input().split())) for _ in range(H)]
    B = [list(map(int,input().split())) for _ in range(H)]

    C = [[0 for j in range(W)] for i in range(H)]

    for i in range(H):
        for j in range(W):
            C[i][j] = abs(A[i][j]-B[i][j])

    dp = [[0 for k in range(6400)] for g in range(H*W)]
    dp[0][C[0][0]] = 1

    for g in range(H*W):
        i,j = divmod(g,W)
        for k in range(6400):
            if not dp[i*W+j][k]:
                continue
            ni,nj = i+1,j+1
            if ni < H:
                if k+C[ni][j]<6400:
                    dp[ni*W+j][k+C[ni][j]] = 1
                dp[ni*W+j][abs(k-C[ni][j])] = 1
            if nj < W:
                if k+C[i][nj]<6400:
                    dp[i*W+nj][k+C[i][nj]] = 1
                dp[i*W+nj][abs(k-C[i][nj])] = 1

    for k in range(6400):
        if dp[-1][k]:
            print(k)
            break

main()

Solution (Python):
def examE():
    H, W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    Diff = [[0] * W for _ in range(H)]
    M = 0
    for i in range(H):
        for j in range(W):
            m = abs(A[i][j] - B[i][j])
            Diff[i][j] = m
            M += m
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][0] |= (1 << Diff[H-1][W-1])
    for i in range(H):
        for j in range(W):
            here = dp[i][j]
            s = Diff[i][j]
            ni = (here << s) | (here >> s)
            ex = 0
            
            for k in range(1, s + 1):
                if (here >> k) & 1:
                    ex |= (1 << (s - k))
            dp[i + 1][j] |= (ni | ex)
            dp[i][j + 1] |= (ni | ex)


    a = dp[H - 1][W - 1]
    ans = 0
    for k in range(M + 1):
        if (a >> k) & 1:
            ans = k
            break
    print(dp)
    print(ans)
    return

def examE2():
    H, W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    dp = [0]*(H*W)
    cur = abs(A[0][0] - B[0][0])
    dp[0] |= (1 << cur)
    for i in range(H):
        for j in range(W):
            now = dp[i*W + j]
            if i < H - 1:
                cur = abs(A[i + 1][j] - B[i + 1][j])
                ni = (now << cur) | (now >> cur)
                ex = 0
                for k in range(1, cur + 1):
                    if (now >> k) & 1:
                        ex |= (1 << (cur - k))
                dp[(i+1)*W +j] |= (ni | ex)
            if j < W - 1:
                cur = abs(A[i][j + 1] - B[i][j + 1])
                ni = (now << cur) | (now >> cur)
                ex = 0
                for k in range(1, cur + 1):
                    if (now >> k) & 1:
                        ex |= (1 << (cur - k))
                dp[i*W +j+1] |= (ni | ex)
    
    ans = inf
    for i,f in enumerate(str(bin(dp[-1]))[::-1]):
        if f=="1":
            ans = i
            break
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE2()

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
A = [lr() for _ in range(H)]
B = [lr() for _ in range(H)]
diff = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        diff[i][j] = abs(A[i][j] - B[i][j])

X = (H+W) * 80
L = X + X + 1 
dp = [[None] * W for _ in range(H)]
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][X+diff[0][0]] = 1; dp[0][0][X-diff[0][0]] = 1 
for h in range(H):
    for w, di in enumerate(diff[h]):
        if h == 0 and w == 0:
            continue
        x = np.zeros(L, np.bool)
        if h > 0:
            x[di:] |= dp[h-1][w][:L-di]
            x[:L-di] |= dp[h-1][w][di:]
        if w > 0:
            x[di:] |= dp[h][w-1][:L-di]
            x[:L-di] |= dp[h][w-1][di:]
        dp[h][w] = x

dp = dp[-1][-1]
possible = np.where(dp)[0] - X
answer = np.abs(possible).min()
print(answer)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')


max_ = 2*(80*80)+1
def transform(x):
    return x+max_


def main():
    H,W=MI()
    A=LLIN(H)
    B=LLIN(H)
    DP = [[0]*W for _ in range(H)]
    DP[0][0] = (1<<transform(abs(A[0][0]-B[0][0]))) | (1<<transform(abs(A[0][0]-B[0][0])))
    for i in range(H):
        for j in range(W):
            ab = abs(A[i][j] - B[i][j])
            if i:
                DP[i][j] |= (DP[i-1][j]>>ab) | (DP[i-1][j]<<ab)
            if j:
                DP[i][j] |= (DP[i][j-1]>>ab) | (DP[i][j-1]<<ab)

    ans = inf
    for val in range(-max_, max_+1):
        if DP[-1][-1]>>transform(val)&1:
            ans = min(ans, abs(val))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
A = []

for i in range(h):
    line = list(map(int, input().split()))
    A.append(line)

for i in range(h):
    line = list(map(int, input().split()))
    for j, num in enumerate(line):
        A[i][j] = abs(A[i][j] - num)

const = 6400
mask = 1 << const
DP = [0]*w
DP[0] = mask >> A[0][0]


def slide_down(y, x):
    bit = DP[x]
    delta = A[y+1][x]
    new1 = bit << delta
    new2 = bit >> delta
    DP[x] = new1 | new2


def slide_right(y, x):
    bit = DP[x]
    delta = A[y][x+1]
    new1 = bit << delta
    new2 = bit >> delta
    DP[x+1] |= new1 | new2


for y in range(h):
    for x in range(w):
        if x < w-1:
            slide_right(y, x)
        if y < h-1:
            slide_down(y, x)

pattern = DP[w-1]
for i in range(81):
    if (pattern >> const+i) & 1 or (pattern >> const-i) & 1:
        print(i)
        exit()

Solution (Python):
import numpy as np
import itertools

H, W = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(H)]
B = [tuple(map(int, input().split())) for _ in range(H)]

D = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]
max_num = 80 * (H + W)
table = np.zeros((H, W, max_num), dtype='bool')
table[0][0][D[0][0]] = True

it = itertools.product(range(H), range(W))
next(it)  
for h, w in it:
    d = D[h][w]
    table[h][w][d:] += table[h - 1][w][:max_num - d] + table[h][w - 1][:max_num - d]
    table[h][w][:max_num - d] += table[h - 1][w][d:] + table[h][w - 1][d:]
    table[h][w][d:0:-1] += table[h - 1][w][:d] + table[h][w - 1][:d]

print(np.amin(*np.where(table[H - 1][W - 1])))

Solution (Python):
import sys
input = sys.stdin.buffer.readline

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

SIZE = 20000
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 << (SIZE + C[0][0]) | 1 << (SIZE - C[0][0])

for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        else:
            dp[i][j] |= dp[i - 1][j] << C[i][j] | dp[i - 1][j] >> C[i][j]
            dp[i][j] |= dp[i][j - 1] << C[i][j] | dp[i][j - 1] >> C[i][j]

for i in range(SIZE):
    if (dp[-1][-1] >> (i + SIZE)) & 1:
        print(i)
        exit()

Solution (Python):
H, W = map(int, input().split())
A = [[0]*W for i in range(H)]
B = [[0]*W for i in range(H)]
for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    A[i][j] = inf[j]

for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    B[i][j] = inf[j]

X = (H+W)*80
dp = [[0]*W for i in range(H)]
d = abs(A[0][0]-B[0][0])
dp[0][0] = 1<<(X+d)

for i in range(H):
  for j in range(W):
    if i==0 and j==0:
      continue
    d = abs(A[i][j]-B[i][j])
    if i!=0:
      dp[i][j] |= dp[i-1][j]>>d
      dp[i][j] |= dp[i-1][j]<<d
    if j!=0:
      dp[i][j] |= dp[i][j-1]>>d
      dp[i][j] |= dp[i][j-1]<<d

s = bin(dp[-1][-1])[2:]
l = len(s)-1
ans = float('inf')
for i in range(l,-1,-1):
  if s[i]=='1':
    m = abs(l-i-X)
    if m<ans:
      ans = m
print(ans)

Solution (Python):
import numpy as np
H,W = map(int,input().split())
A = [[0]*W for i in range(H)]
B = [[0]*W for i in range(H)]
for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    A[i][j] = inf[j]
    
for i in range(H):
  inf = [int(c) for c in input().split()]
  for j in range(W):
    B[i][j] = inf[j]

X = (H + W) * 80
L = X + X + 1

dp = [[0] * W for _ in range(H)]
d = abs(A[0][0] - B[0][0])
dp[0][0] = np.zeros(L,np.bool)
dp[0][0][X+d] = 1
for h in range(H):
    for w,(a,b) in enumerate(zip(A[h],B[h])):
        if h == w == 0:
            continue
        d = abs(a - b)
        x = np.zeros(L,np.bool)
        if h != 0:
            x[d:] |= dp[h-1][w][:L-d]
            x[:L-d] |= dp[h-1][w][d:]
        if w != 0:
            x[d:] |= dp[h][w-1][:L-d]
            x[:L-d] |= dp[h][w-1][d:]
        dp[h][w] = x

dp2 = dp[-1][-1]
can_make = np.where(dp2)[0] - X

answer = np.abs(can_make).min()
print(answer)

Solution (Python):
maxV = 80*(80+80)

H, W = map(int, input().split())
Ass = [tuple(map(int, input().split())) for _ in range(H)]
Bss = [tuple(map(int, input().split())) for _ in range(H)]

dp = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        A, B = Ass[i][j], Bss[i][j]
        if A > B:
            A, B = B, A
        if i == 0 and j == 0:
            dp[i][j] = 1<<(maxV+B-A) | 1<<(maxV-B+A)
        if i > 0:
            dp[i][j] |= dp[i-1][j]<<(B-A) | dp[i-1][j]>>(B-A)
        if j > 0:
            dp[i][j] |= dp[i][j-1]<<(B-A) | dp[i][j-1]>>(B-A)

bitset = dp[-1][-1]
mask = 1<<(2*maxV)
ans = maxV
for i in range(-maxV, maxV+1):
    if bitset & mask:
        ans = min(ans, abs(i))
    mask >>= 1

print(ans)