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 numpy as np
i8 = np.int64
i4 = np.int32

def calc(dp1, dp2, k):
    dp2[k:] += dp1[:dp1.shape[0]-k]
    dp2[:dp2.shape[0]-k] += dp1[k:]

def solve(z, dp):
    zero = dp.shape[2] // 2
    dp[0, 0, zero + z[0, 0]] = 1
    dp[0, 0, zero - z[0, 0]] = 1
    for x in range(1, z.shape[1]):
        calc(dp[0, x - 1], dp[0, x], z[0, x])
    for y in range(1, z.shape[0]):
        calc(dp[y - 1, 0], dp[y, 0], z[y, 0])
        for x in range(1, z.shape[1]):
            calc(dp[y, x - 1], dp[y, x], z[y, x])
            calc(dp[y - 1, x], dp[y, x], z[y, x])
            if (x + y) % 50 == 0:
                dp[y, x] = dp[y, x] > 0
    for i in range(zero, dp.shape[2]):
        if dp[dp.shape[0] - 1, dp.shape[1] - 1, i] > 0:
            return i - zero
    return -1

def main2():
    stdin = open('/dev/stdin')
    H, W = map(int, stdin.readline().split())
    a = np.empty((H, W), i8)
    b = np.empty((H, W), i8)
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            a[i, j] = c
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            b[i, j] = c
    z = np.abs(a - b)
    dp = np.zeros((H, W, 80 * 80 *2 + 1), i8)
    ans = solve(z, dp)
    print(ans)


main2()

Solution (Python):
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [None] * H
for i in range(H):
    A[i] = list(map(int, input().split()))
for i in range(H):
    B[i] = list(map(int, input().split()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        d = C[i-1][j-1]
        x = int('0'+bin((dp[i-1][j]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        y = int('0'+bin((dp[i][j-1]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        dp[i][j] = (dp[i-1][j] >> d) | (dp[i-1][j] << d) | (dp[i][j-1] >> d) | (dp[i][j-1] << d) | x | y
for i, v in enumerate(bin(dp[H][W])[::-1]):
    if v == '1':
        print(i)
        break

Solution (Python):
import numpy as np
i8 = np.int64
i4 = np.int32

def calc(dp1, dp2, k):
    dp2[k:] += dp1[:dp1.shape[0]-k]
    dp2[:dp2.shape[0]-k] += dp1[k:]

def solve(z, dp):
    zero = dp.shape[2] // 2
    dp[0, 0, zero + z[0, 0]] = 1
    dp[0, 0, zero - z[0, 0]] = 1
    for x in range(1, z.shape[1]):
        calc(dp[0, x - 1], dp[0, x], z[0, x])
    for y in range(1, z.shape[0]):
        calc(dp[y - 1, 0], dp[y, 0], z[y, 0])
        for x in range(1, z.shape[1]):
            calc(dp[y, x - 1], dp[y, x], z[y, x])
            calc(dp[y - 1, x], dp[y, x], z[y, x])
            if (x + y) % 10 == 0:
                dp[y, x] = dp[y, x] > 0
    for i in range(zero, dp.shape[2]):
        if dp[dp.shape[0] - 1, dp.shape[1] - 1, i] > 0:
            return i - zero
    return -1

def main2():
    stdin = open('/dev/stdin')
    H, W = map(int, stdin.readline().split())
    a = np.empty((H, W), i8)
    b = np.empty((H, W), i8)
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            a[i, j] = c
    for i in range(H):
        for j, c in enumerate(map(int, stdin.readline().split())):
            b[i, j] = c
    z = np.abs(a - b)
    dp = np.zeros((H, W, 80 * 80 *2 + 1), i8)
    ans = solve(z, dp)
    print(ans)


main2()

Solution (Python):
M = 6400
mid = M//2
INF = 10**18

H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([abs(a-b) for a,b in zip(As[i],bs)])



dp = [[0]*W for j in range(H)]
dp[0][0] = 1 << (mid+diffs[0][0]) 
for i in range(H):
    for j in range(W):
        
        if i+1 < H:
            d = diffs[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d  
            dp[i+1][j] |= dp[i][j] << d  
        
        if j+1 < W:
            d = diffs[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d
            dp[i][j+1] |= dp[i][j] << d

ans = INF
for i in range(M):
    if dp[H-1][W-1] >> i & 1:
        
        ans = min(ans, abs(i-mid))
print(ans)

Solution (Python):
M = 6400*4
mid = M//2
INF = 10**18

H,W = map(int, input().split())
As = []
for i in range(H):
    As.append(list(map(int, input().split())))
diffs = []
for i in range(H):
    bs = list(map(int, input().split()))
    diffs.append([abs(a-b) for a,b in zip(As[i],bs)])



dp = [[0]*W for j in range(H)]
dp[0][0] = 1 << (mid+diffs[0][0]) 
for i in range(H):
    for j in range(W):
        
        if i+1 < H:
            d = diffs[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d  
            dp[i+1][j] |= dp[i][j] << d  
        
        if j+1 < W:
            d = diffs[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d
            dp[i][j+1] |= dp[i][j] << d

ans = INF
for i in range(M):
    if dp[H-1][W-1] >> i & 1:
        
        ans = min(ans, abs(i-mid))
print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,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
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', '')
def main():
    H,W=MI()
    A=LLIN(H)
    B=LLIN(H)
    X=80*(H+W)
    can = [[0]*W for _ in range(H)]
    can[0][0] += 1<<(X-abs(A[0][0]-B[0][0]))
    for h in range(H):
        for w in range(W):
            absol = abs(A[h][w]-B[h][w])
            if h:
                can[h][w]|=can[h-1][w]<<absol
                can[h][w]|=can[h-1][w]>>absol
            if w:
                can[h][w]|=can[h][w-1]<<absol
                can[h][w]|=can[h][w-1]>>absol
    for i in range(160*(H+W)+5):
        if can[-1][-1] & ((1<<X<<i) | (1<<X>>i)):
            print(i)
            break

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [None] * H
for i in range(H):
    A[i] = list(map(int, input().split()))
for i in range(H):
    B[i] = list(map(int, input().split()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 80*(80+80)
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        d = C[i-1][j-1]
        if d != 0:
            x = int(bin((dp[i-1][j]&(2**d-1))+2**d)[::-1][:d], 2)<<1
            y = int(bin((dp[i][j-1]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        else:
            x=y=0
        
        dp[i][j] = (dp[i-1][j] >> d) | (dp[i-1][j] << d) | (dp[i][j-1] >> d) | (dp[i][j-1] << d) | x | y
        

for i, v in enumerate(bin(dp[H][W])[::-1]):
    if v == '1':
        print(i)
        break

Solution (Python):
H, W = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(H)]
B = [[int(a) for a in input().split()] for _ in range(H)]
C = [[A[i][j] - B[i][j] for j in range(W)] for i in range(H)]
X = [[0] * (W) for _ in range(H)]
X[0][0] = (1 << 80 + C[0][0]) | (1 << 80 - C[0][0])
for i in range(H):
    for j in range(W):
        if i:
            X[i][j] |= (X[i-1][j] << 80 + C[i][j]) | (X[i-1][j] << 80 - C[i][j])
        if j:
            X[i][j] |= (X[i][j-1] << 80 + C[i][j]) | (X[i][j-1] << 80 - C[i][j])
s = bin(X[-1][-1] + (1<<13000))
mi = 1<<100
for i in range(len(s)):
    if s[-i-1] == "1":
        mi = min(mi, abs(i-(H+W-1)*80))
print(mi)

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

def honya(y, d):
  t = (1 << d + 1) - 1
  t = y & t
  k = 0
  for i in range(d):
    k += t & 1
    t >>= 1
    k <<= 1
  return k

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

DP = [[0] * W for _ in range(H)]

def nasu(x, y, d):
  t = (1 << (d + 1)) - 1 & y
  return (x | (y << d) | (y >> d) | honya(y, d)) & mask
  

mask = (1 << M) - 1
DP[0][0] = 1 << D[0][0]
for i in range(H):
  for j in range(W):
    if i + 1 < H:
      DP[i + 1][j] = nasu(DP[i + 1][j], DP[i][j], D[i + 1][j])
    if j + 1 < W:
      DP[i][j + 1] = nasu(DP[i][j + 1], DP[i][j], D[i][j + 1])

t = DP[-1][-1]
for i in range(M):
  if t & 1:
    print(i)
    break
  t >>= 1

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def bin_out(aa):
    bb = [format(a, "b") for a in aa]
    print(bb)

def main():
    h, w = MI()
    aa = LLI(h)
    bb = LLI(h)
    max_val=6400
    zero = 1 << max_val
    dp = [0] * w
    dp[0] = zero
    
    for i, (ar, br) in enumerate(zip(aa, bb)):
        for j, (a, b) in enumerate(zip(ar, br)):
            d = abs(a - b)
            if j > 0: dp[j] |= dp[j - 1]
            dp[j] = dp[j] << d | dp[j] >> d
        
    goal = dp[-1]
    for ans in range(max_val + 1):
        if goal & zero << ans or goal & zero >> ans:
            print(ans)
            break

main()

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

dp = [0]*(w+1)
dp[0] = 1
for i in range(h):
  for j in range(w):
    cur,par = g[i][j],dp[j]|dp[j-1]
    dp[j] = par<<cur&mask|fold(par,cur)
for i in range(m):
  if dp[-2]&(1<<i):
    print(i)
    break

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

import itertools
import numpy as np

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

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

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

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

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)]

mask = (1<<12801) - 1

dp = [[0]*(w+1) for _ in range(h+1)]
dp[0][0] = 1
for i in range(h):
  for j in range(w):
    cur,par = g[i][j],dp[i][j]
    pos = (par<<cur)|fold(par,cur)
    pos &= mask
    dp[i+1][j] |= pos
    dp[i][j+1] |= pos
for i in range(12801):
  if dp[-1][-2]&(1<<i):
    print(i)
    break

Solution (Python):
def main():
  e=enumerate
  (h,w),*a=[list(map(int,t.split()))for t in open(0)]
  dp=[0]*w
  c=12800
  for i,a in e(zip(a,a[h:])):
    for j,(x,y)in e(zip(*a)):
      x=abs(x-y)
      t=0
      if j:t|=dp[j-1]<<x|dp[j-1]>>x
      if i:t|=dp[j]<<x|dp[j]>>x
      dp[j]=t if i+j else 2**c<<x
  *a,=map(int,(bin(dp[w-1])[2:]).zfill(c-~c))
  print([i for i,(f,g)in e(zip(a[c:],a[c::-1]))if f+g][0])
main()

Solution (Python):
H, W = [int(x) for x in input().split()]

A = [[0]*W for i in range(H)]
for c in [1, -1]:
    for i in range(H):
        arr = [int(x) for x in input().split()]
        for j in range(W):
            A[i][j] += arr[j] * c

M = 160*80
dp = [[0]*W for i in range(H)]
dp[0][0] = 1 << M
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] |= dp[i-1][j]
        if j > 0:
            dp[i][j] |= dp[i][j-1]
        a = abs(A[i][j])
        dp[i][j] = (dp[i][j] << a) | (dp[i][j] >> a)

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

Solution (Python):
e=enumerate
(h,w),*a=[list(map(int,t.split()))for t in open(0)]
dp=[0]*w
c=12800
for i,a in e(zip(a,a[h:])):
  for j,(x,y)in e(zip(*a)):
    x=abs(x-y)
    t=0
    if j:t|=dp[j-1]<<x|dp[j-1]>>x
    if i:t|=dp[j]<<x|dp[j]>>x
    dp[j]=t if i+j else 2**c<<x
*a,=map(int,(bin(dp[w-1])[2:]).zfill(c-~c))
print(min(i for i,(f,g)in e(zip(a[c:],a[c::-1]))if f+g))

Solution (Python):
e=enumerate
(h,w),*a=[list(map(int,t.split()))for t in open(0)]
dp=[0]*w
c=12800
for i,a in e(zip(a,a[h:])):
  for j,(x,y)in e(zip(*a)):
    x=abs(x-y)
    t=0
    if j:t|=dp[j-1]<<x|dp[j-1]>>x
    if i:t|=dp[j]<<x|dp[j]>>x
    dp[j]=t if i+j else 2**c<<x
*a,=map(int,(bin(dp[w-1])[2:]).zfill(25601))
print(min(i for i,(f,g)in e(zip(a[12800:],a[12800::-1]))if f+g))

Solution (Python):
e=enumerate
(h,w),*a=[list(map(int,t.split()))for t in open(0)]
dp=[0]*w
c=12800
for i,a in e(zip(a,a[h:])):
  for j,(x,y)in e(zip(*a)):
    x=abs(x-y)
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t if i+j else 2**c<<x
*a,=map(int,(bin(dp[w-1])[2:]).zfill(25601))
print(min([i for i,f in e(a[12800:])if f]+[i for i,f in e(a[12800::-1])if f]))

Solution (Python):
e=enumerate
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)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))

Solution (Python):
e=enumerate
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)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))

Solution (Python):
def inpl(): return list(map(int, input().split()))

H, W = inpl()
A = [inpl() for _ in range(H)]
B = [inpl() for _ in range(H)]

DP = [[0 for _ in range(W+1)] for _ in range(H+1)]
DP[0][0] = 1 << 12800

for h in range(H):
    for w in range(W):
        d = abs(A[h][w] - B[h][w])
        DP[h+1][w] |= DP[h][w] >> d
        DP[h+1][w] |= DP[h][w] << d
        DP[h][w+1] |= DP[h][w] >> d
        DP[h][w+1] |= DP[h][w] << d
l = 1 << 12800
r = 1 << 12800
for i in range(12801):
    if (DP[-1][-2]& l) | (DP[-1][-2] & r):
        print(i)
        break
    l = l << 1
    r = r >> 1

Solution (Python):
H, W = map(int, input().split())
M = (H + W) * 80

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

dp = [[0] * W for _ in range(H)]
dp[0][0] = (1 << (M - abs(A[0][0] - B[0][0])))

for h in range(H):
    for w, (a, b) in enumerate(zip(A[h], B[h])):
        d = abs(a - b)
        mask = 0
        if h > 0:
            mask |= (dp[h - 1][w] << d)
            mask |= (dp[h - 1][w] >> d)
        if w > 0:
            mask |= (dp[h][w - 1] << d)
            mask |= (dp[h][w - 1] >> d)
        dp[h][w] |= mask

state = dp[-1][-1]
nums = []
for digit, b in enumerate(bin(state)[2:][:: -1]):
    if b == '1':
        nums.append(digit - M)
ans = min(abs(n) for n in nums)
print(ans)

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

for i in range(H):
	a = list(map(int,input().split()))
	A[i] = a
for i in range(H):
	b = list(map(int,input().split()))
	B[i] = b

D = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
R = 160*80
"""
dp = [[[False for k in range(R)] for j in range(W)] for i in range(H)]
dp[0][0][D[0][0]] = True
for i in range(H):
	for j in range(W):
		r = 80 * (i+j+2)
		for n in range(r):
			if not dp[i][j][n]:
				continue
			if j != W-1:
				d = D[i][j+1]
				dp[i][j+1][n+d] = True
				dp[i][j+1][abs(n-d)] = True
			if i != H-1:
				d = D[i+1][j]
				dp[i+1][j][n+d] = True
				dp[i+1][j][abs(n-d)] = True

"""
dp = [[0 for j in range(W)] for i in range(H)]
dp[0][0] = 2**(R + D[0][0]) | 2**(R - D[0][0])
for i in range(H):
	for j in range(W):
		if j != W-1:
			d = D[i][j+1]
			dp[i][j+1] |= (dp[i][j] << d | dp[i][j] >> d)
		if i != H-1:
			d = D[i+1][j]
			dp[i+1][j] |= (dp[i][j] << d | dp[i][j] >> d)
h,w = H-1, W-1
for i in range(R):
	mask = 2 ** (R+i) | 2 ** (R-i)
	if dp[h][w] & mask > 0:
		print(i)
		exit()

Solution (Python):

''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]


h,w = _ia()
ab = []
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)


dp = [[None for _ in range(w)] for _ in range(h)]
dp[0][0] = {ab[0][0]}
hw1 = h + w - 1
for ij in range(1,hw1):
    iend = ( hw1 - ij ) * 80
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        
        ref = set()
        if i>0: ref|= dp[i-1][j]
        if j>0: ref|= dp[i][j-1]
        
        x = ab[i][j]
        nxt = dp[i][j] = set()
        for idx in ref:
            ix = abs(idx-x)
            if ix<=iend: nxt.add(ix)
            ix = idx + x
            if ix<=iend: nxt.add(ix)
            

print(min(dp[h-1][w-1]))

Solution (Python):
import sys
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)]
X = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
dp1 = [set() for _ in range(W)]
dp1[0].add(X[0][0])
dp2 = [set() for _ in range(W)]
dplimit = [[0] * W for _ in range(H)]
dplimit[-1][-1] = 80
for i in range(H - 1, -1, -1):
  for j in range(W - 1, -1, -1):
    x = X[i][j]
    if i > 0: dplimit[i - 1][j] = max(dplimit[i - 1][j], dplimit[i][j] + x)
    if j > 0: dplimit[i][j - 1] = max(dplimit[i][j - 1], dplimit[i][j] + x)
for i in range(H):
  if i % 2 == 0:
    dp2 = [set() for _ in range(W)]
  else: dp1 = [set() for _ in range(W)]
  for j in range(W):
    if i % 2 == 0:
      for k in dp1[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp2[j].add(u)
          if v <= dplimit[i][j]: dp2[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp1[j + 1].add(u)
          if v <= dplimit[i][j]: dp1[j + 1].add(v)
    else:
      for k in dp2[j]:
        if i + 1 < H:
          u = k + X[i + 1][j]
          v = abs(k - X[i + 1][j])
          if u <= dplimit[i][j]: dp1[j].add(u)
          if v <= dplimit[i][j]: dp1[j].add(v)
        if j + 1 < W:
          u = k + X[i][j + 1]
          v = abs(k - X[i][j + 1])
          if u <= dplimit[i][j]: dp2[j + 1].add(u)
          if v <= dplimit[i][j]: dp2[j + 1].add(v)
res = float("inf")
if H % 2:
  for k in dp1[-1]: res = min(k, res)
else:
  for k in dp2[-1]: res = min(k, res)
print(res)

Solution (Python):

import sys

def solve(H: int, W: int, A: "List[List[int]]", B: "List[List[int]]"):
    SA=[[0]*W for i in range(H)]
    MAX = (H+W)*80
    for i in range(H):
        for j in range(W):
            SA[i][j]=abs(A[i][j]-B[i][j])

    DP=[[0 for i in range(W)] for j in range(H)]
    DP[0][0]=1<<MAX+SA[0][0]

    for i in range(H):
        for j in range(W):
            tempbit=DP[i][j]
            if i<H-1:
                DP[i+1][j]|=tempbit<<SA[i+1][j]
                DP[i+1][j]|=tempbit>>SA[i+1][j]

            if j<W-1:
                DP[i][j+1]|=tempbit<<SA[i][j+1]
                DP[i][j+1]|=tempbit>>SA[i][j+1]

    ANS=1<<MAX*2
    for i in range(MAX*2+1):
        if 1<<i & DP[-1][-1]!=0:
            ANS=min(ANS,abs(i-MAX))

    print(ANS)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  
    B = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  
    solve(H, W, A, B)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    ofs=6400
    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)]
    dp=[[0]*w for _ in range(h)]
    x=abs(A[0][0]-B[0][0])
    dp[0][0]|=((1<<(ofs+x))|(1<<(ofs-x)))

    from itertools import product
    for i,j in product(range(h),range(w)):
        x=abs(A[i][j]-B[i][j])
        t=0
        if(i-1>=0):
            t|=dp[i-1][j]
        if(j-1>=0):
            t|=dp[i][j-1]
        dp[i][j]|=((t<<x)|(t>>x))

    for i,s in enumerate(bin(dp[-1][-1])[-ofs-1:]):
        if(s=='1'):
            print(i)
            return
                    
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    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)]
    dp=[[0]*w for _ in range(h)]
    x=abs(A[0][0]-B[0][0])
    offset=12800
    dp[0][0]|=1<<(x+offset)
    dp[0][0]|=1<<(-x+offset)

    from itertools import product
    for i,j in product(range(h),range(w)):
        if(i==0 and j==0): continue
        x=abs(A[i][j]-B[i][j])
        S=0
        if(i>0): S|=dp[i-1][j]
        if(j>0): S|=dp[i][j-1]
        dp[i][j]=(S<<x)|(S>>x)

    for i in range(12800):
        if((dp[-1][-1]>>(i+offset))&1):
            print(i)
            return
resolve()

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

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)]

SA=[[0]*W for i in range(H)]

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

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

DP[0][0]=1<<(H+W)*80+SA[0][0]

for i in range(H):
    for j in range(W):
        tempbit=DP[i][j]
        if i+1<H:
            DP[i+1][j]|=tempbit<<SA[i+1][j]
            DP[i+1][j]|=tempbit>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=tempbit<<SA[i][j+1]
            DP[i][j+1]|=tempbit>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*160+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-(H+W)*80))

print(ANS)

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

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)]

SA=[[0]*W for i in range(H)]

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

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

DP[0][0]=1<<(H+W)*80+SA[0][0]

for i in range(H):
    for j in range(W):
        tempbit=DP[i][j]
        if i+1<H:
            DP[i+1][j]|=tempbit<<SA[i+1][j]
            DP[i+1][j]|=tempbit>>SA[i+1][j]

        if j+1<W:
            DP[i][j+1]|=tempbit<<SA[i][j+1]
            DP[i][j+1]|=tempbit>>SA[i][j+1]

ANS=1<<30
for i in range((H+W)*160+1):
    if 1<<i & DP[-1][-1]!=0:
        ANS=min(ANS,abs(i-(H+W)*80))

print(ANS)

Solution (Python):

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    H,W = list(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)]

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



    DP = [[[0]*(80*160+1) for j in range(W)] for i in range(H)]

    DP[0][0][C[0][0]] = 1

    for j in range(1,W):
        for k in range(80*160+1):
            if DP[0][j-1][k] == 1:
                DP[0][j][abs(k-C[0][j])] = 1
                DP[0][j][abs(k+C[0][j])] = 1

    for i in range(1,H):
        for k in range(80*160+1):
            if DP[i-1][0][k] == 1:
                DP[i][0][abs(k-C[i][0])] = 1
                DP[i][0][abs(k+C[i][0])] = 1


    for i in range(1,H):
        for j in range(1,W):
            for k in range(80*160+1):
                if DP[i][j-1][k] == 1 or DP[i-1][j][k] == 1:
                    DP[i][j][abs(k-C[i][j])] = 1
                    DP[i][j][abs(k+C[i][j])] = 1

    for i in range(80*160+1):
        if DP[H-1][W-1][i]==1:
            print(i)
            break

if __name__ == '__main__':
    main()

Solution (Python):
H,W = map(int,input().split())
A = [list(map(int,input().split()))for _ in range(H)]
for i in range(H):
    b = list(map(int,input().split()))
    for j in range(W):
        A[i][j] = abs(A[i][j]-b[j])
NUM = 6400
DP = [[[0]*NUM for i in range(W)]for j in range(H)]
DP[0][0][A[0][0]] = 1
i = 0
for j in range(W-1):
    a = A[i][j+1]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i][j+1][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i][j+1][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i][j+1][k+a] = 1
j = 0
for i in range(H-1):
    a = A[i+1][j]
    for k in range(NUM):
        if DP[i][j][k] == 1:
            if 0 <= a-k < NUM:
                DP[i+1][j][a-k] = 1
            if 0 <= k-a < NUM:
                DP[i+1][j][k-a] = 1
            if 0 <= k+a < NUM:
                DP[i+1][j][k+a] = 1
for i in range(H-1):
    for j in range(W-1):
        a = A[i+1][j+1]
        for k in range(NUM):
            if DP[i+1][j][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1
            if DP[i][j+1][k] == 1:
                if 0 <= a-k < NUM:
                    DP[i+1][j+1][a-k] = 1
                if 0 <= k-a < NUM:
                    DP[i+1][j+1][k-a] = 1
                if 0 <= k+a < NUM:
                    DP[i+1][j+1][k+a] = 1

print(DP[-1][-1].index(1))

Solution (Python):
from itertools import product

def offset(a, b):
    result = 0
    if b == 0: return 0
    for i in range(b+1):
        if (a >> i) & 1:
            result |= (1 << b) >> i
    return result

H, W = map(int, input().split())
diff = [list(map(int, input().split())) for _ in range(H)]
M = 80
for i in range(H):
    B = list(map(int, input().split()))
    for j in range(W):
        diff[i][j] = abs(diff[i][j] - B[j])
dp = [[0]*W for _ in range(H)]
dp[0][0] = 1 << diff[0][0]
for i, j in product(range(H), range(W)):
    if (i, j) == (H-1, W-1): break
    if i+1 < H:
        k = diff[i+1][j]
        dp[i+1][j] |= (dp[i][j] >> k) | (dp[i][j] << k) | (offset(dp[i][j], k))
    if j+1 < W:
        k = diff[i][j+1]
        dp[i][j+1] |= (dp[i][j] >> k) | (dp[i][j] << k) | (offset(dp[i][j], k))
ans = dp[H-1][W-1]
print((ans & -ans).bit_length() - 1)

Solution (Python):
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
B = []
C = []
for y in range(H):
    B.append(list(map(int, input().split())))
    C.append(list(abs(a-b) for (a, b) in zip(A[y], B[y])))
VMAX = 80*159+1
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] |= 1 << C[0][0]
for y in range(H):
    for x in range(W):
        if y==0 and x==0:
            continue
        if y-1 >= 0:
            dp[y][x] |= dp[y-1][x] << C[y][x]
            dp[y][x] |= dp[y-1][x] >> C[y][x]
            d = C[y][x]+1
            r = format(dp[y-1][x] & (2**d-1), '0'+str(d)+'b')
            r = r[::-1]
            dp[y][x] |= int(r, 2)
        if x-1 >= 0:
            dp[y][x] |= dp[y][x-1] << C[y][x]
            dp[y][x] |= dp[y][x-1] >> C[y][x]
            d = C[y][x]+1
            r = format(dp[y][x-1] & (2**d-1), '0'+str(d)+'b')
            r = r[::-1]
            dp[y][x] |= int(r, 2)
ans = -1
for v in range(VMAX):
    if dp[-1][-1] >> v & 1:
        ans = v
        break
print(ans)