solutions: ["import sys\nfrom collections import defaultdict\nfrom collections import deque\nimport numpy as np\nimport heapq\nfrom heapq import heappush, heappop\nimport itertools\nimport math\nimport copy\n(H, W) = list(map(int, input().split()))\nA = []\nB = []\nfor _ in range(H):\n\ta = list(map(int, input().split()))\n\tA.append(a)\nfor _ in range(H):\n\tb = list(map(int, input().split()))\n\tB.append(b)\nC = []\nfor i in range(H):\n\tcs = []\n\tfor j in range(W):\n\t\tc = abs(A[i][j] - B[i][j])\n\t\tcs.append(c)\n\tC.append(cs)\nX = (H + W) * 80\nL = X + X + 1\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = np.zeros(L, np.bool)\nd = C[0][0]\ndp[0][0][X + d] = 1\ndp[0][0][X - d] = 1\nfor r in range(H):\n\tfor c in range(W):\n\t\tif r == 0 and c == 0:\n\t\t\tcontinue\n\t\tl = np.zeros(L, np.bool)\n\t\td = C[r][c]\n\t\tif r != 0:\n\t\t\tl[d:] |= dp[r - 1][c][:L - d]\n\t\t\tl[:L - d] |= dp[r - 1][c][d:]\n\t\tif c != 0:\n\t\t\tl[d:] |= dp[r][c - 1][:L - d]\n\t\t\tl[:L - d] |= dp[r][c - 1][d:]\n\t\tdp[r][c] = l\ndp = dp[-1][-1]\nd = np.where(dp)[0] - X\nans = np.abs(d).min()\nprint(ans)\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\nsys.setrecursionlimit(10 ** 7)\n(H, W) = map(int, input().split())\nA = [[int(x) for x in input().split()] for _ in range(H)]\nB = [[int(x) for x in input().split()] for _ in range(H)]\nC = [[0] * W for _ in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\ncenter = 80 * (H + W)\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = 1 << center - C[0][0] | 1 << center + C[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i:\n\t\t\tdp[i][j] |= dp[i - 1][j] << C[i][j]\n\t\t\tdp[i][j] |= dp[i - 1][j] >> C[i][j]\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << C[i][j]\n\t\t\tdp[i][j] |= dp[i][j - 1] >> C[i][j]\nans = center * 2\nfor i in range(center * 2):\n\tif dp[H - 1][W - 1] >> i & 1:\n\t\tans = min(ans, abs(i - center))\nprint(ans)\n", "def main():\n\te = enumerate\n\t((h, w), *a) = [list(map(int, t.split())) for t in open(0)]\n\tdp = [0] * w\n\tc = 12800\n\tfor (i, a) in e(zip(a, a[h:])):\n\t\tfor (j, (x, y)) in e(zip(*a)):\n\t\t\tx = abs(x - y)\n\t\t\tt = 0\n\t\t\tif j:\n\t\t\t\tt |= dp[j - 1] << x | dp[j - 1] >> x\n\t\t\tif i:\n\t\t\t\tt |= dp[j] << x | dp[j] >> x\n\t\t\tdp[j] = t if i + j else 2 ** c << x\n\t(*a,) = map(int, bin(dp[w - 1])[2:].zfill(c - ~c))\n\tprint([i for (i, (f, g)) in e(zip(a[c:], a[c::-1])) if f + g][0])\nmain()\n", "import sys\nimport numpy as np\nsr = lambda : sys.stdin.readline().rstrip()\nir = lambda : int(sr())\nlr = lambda : list(map(int, sr().split()))\n(H, W) = lr()\nA = np.array([lr() for _ in range(H)])\nB = np.array([lr() for _ in range(H)])\ndiff = np.abs(A - B).tolist()\nX = (H + W) * 80\nL = X + X + 1\ndp = [[None] * W for _ in range(H)]\ndp[0][0] = np.zeros(L, np.bool)\ndp[0][0][X + diff[0][0]] = 1\ndp[0][0][X - diff[0][0]] = 1\nfor h in range(H):\n\tfor w in range(W):\n\t\tif h == 0 and w == 0:\n\t\t\tcontinue\n\t\tdi = diff[h][w]\n\t\tx = np.zeros(L, np.bool)\n\t\tif h > 0:\n\t\t\tx[di:] |= dp[h - 1][w][:L - di]\n\t\t\tx[:L - di] |= dp[h - 1][w][di:]\n\t\tif w > 0:\n\t\t\tx[di:] |= dp[h][w - 1][:L - di]\n\t\t\tx[:L - di] |= dp[h][w - 1][di:]\n\t\tdp[h][w] = x\ndp = dp[-1][-1][X:]\npossible = np.where(dp == 1)[0]\nanswer = possible.min()\nprint(answer)\n", "import sys\ninput = sys.stdin.readline\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\ndiff = [[0] * w for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tdiff[i][j] = abs(a[i][j] - b[i][j])\ndp = [0] * (h * w)\ndp[0] |= 1 << 13000 + diff[0][0]\ndp[0] |= 1 << 13000 - diff[0][0]\nfor k in range(h * w):\n\ti = k // w\n\tj = k % w\n\tif i + 1 < h:\n\t\ttmp1 = diff[i + 1][j]\n\t\tdp[k + w] |= dp[k] << tmp1\n\t\tdp[k + w] |= dp[k] >> tmp1\n\tif j + 1 < w:\n\t\ttmp2 = diff[i][j + 1]\n\t\tdp[k + 1] |= dp[k] << tmp2\n\t\tdp[k + 1] |= dp[k] >> tmp2\nans = 10 ** 9\nfor i in range(81):\n\tif dp[w * h - 1] >> 13000 + i & 1:\n\t\tans = min(ans, i)\nfor i in range(81):\n\tif dp[w * h - 1] >> 13000 - i & 1:\n\t\tans = min(ans, i)\nprint(ans)\n", "(h, w) = map(int, input().split())\nA = []\nfor i in range(h):\n\tline = list(map(int, input().split()))\n\tA.append(line)\nfor i in range(h):\n\tline = list(map(int, input().split()))\n\tfor (j, num) in enumerate(line):\n\t\tA[i][j] = abs(A[i][j] - num)\nconst = 6400\nmask = 1 << const\nDP = [0] * w\nDP[0] = mask >> A[0][0]\n\ndef slide_down(y, x):\n\tbit = DP[x]\n\tdelta = A[y + 1][x]\n\tnew1 = bit << delta\n\tnew2 = bit >> delta\n\tDP[x] = new1 | new2\n\ndef slide_right(y, x):\n\tbit = DP[x]\n\tdelta = A[y][x + 1]\n\tnew1 = bit << delta\n\tnew2 = bit >> delta\n\tDP[x + 1] |= new1 | new2\nfor y in range(h):\n\tfor x in range(w):\n\t\tif x < w - 1:\n\t\t\tslide_right(y, x)\n\t\tif y < h - 1:\n\t\t\tslide_down(y, x)\npattern = DP[w - 1]\nfor i in range(81):\n\tif pattern >> const + i & 1 or pattern >> const - i & 1:\n\t\tprint(i)\n\t\texit()\n", "(h, w) = list(map(int, input().split()))\nA = [list(map(int, input().split())) for i in range(h)]\nB = [list(map(int, input().split())) for i in range(h)]\nC = [[0] * w for _ in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\nimport numpy as np\ndp = [[0] * (w + 1) for _ in range(h + 1)]\nimport numpy as np\nd = 80 * (h + w - 1) + 1\nD = 2 * d + 1\ndp[0][0] = np.zeros(D, np.bool)\ndp[0][0][C[0][0] + d] = 1\nfor i in range(h):\n\tfor j in range(w):\n\t\tc = C[i][j]\n\t\tif i == 0 and j == 0:\n\t\t\tcontinue\n\t\telif i == 0:\n\t\t\tb = np.zeros(D, np.bool)\n\t\t\tb[c:] |= dp[i][j - 1][:D - c]\n\t\t\tb[:D - c] |= dp[i][j - 1][c:]\n\t\telif j == 0:\n\t\t\tb = np.zeros(D, np.bool)\n\t\t\tb[c:] |= dp[i - 1][j][:D - c]\n\t\t\tb[:D - c] |= dp[i - 1][j][c:]\n\t\telse:\n\t\t\tb = np.zeros(D, np.bool)\n\t\t\tb[c:] |= dp[i][j - 1][:D - c]\n\t\t\tb[:D - c] |= dp[i][j - 1][c:]\n\t\t\tb[c:] |= dp[i - 1][j][:D - c]\n\t\t\tb[:D - c] |= dp[i - 1][j][c:]\n\t\tdp[i][j] = b\nans = float('inf')\nfor i in range(D):\n\tif dp[h - 1][w - 1][i]:\n\t\tans = min(ans, abs(i - d))\nprint(ans)\n", "(h, w) = map(int, input().split())\nbitdp = [[0 for j in range(w)] for i in range(h)]\nal = []\nbl = []\nfor _ in range(h):\n\ta = list(map(int, input().split()))\n\tal.append(a)\nfor _ in range(h):\n\tb = list(map(int, input().split()))\n\tbl.append(b)\nabl = [[] for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tabl[i].append(abs(al[i][j] - bl[i][j]))\nbitdp[0][0] = 1 << h * w + abl[0][0]\nfor i in range(h):\n\tfor j in range(w):\n\t\tif j != w - 1:\n\t\t\tbitdp[i][j + 1] |= bitdp[i][j] << abl[i][j + 1] | bitdp[i][j] >> abl[i][j + 1]\n\t\tif i != h - 1:\n\t\t\tbitdp[i + 1][j] |= bitdp[i][j] << abl[i + 1][j] | bitdp[i][j] >> abl[i + 1][j]\nans = []\nfor i in range(h * w * 2 + 1):\n\tif bitdp[-1][-1] >> i & 1:\n\t\tans.append(abs(h * w - i))\nprint(min(ans))\n", "import sys\ninput = sys.stdin.readline\n(h, w) = map(int, input().split())\nred = [list(map(int, input().split())) + [0] for i in range(h)] + [[0 for i in range(w + 1)]]\nblue = [list(map(int, input().split())) + [0] for i in range(h)] + [[0 for i in range(w + 1)]]\nfield = [[[0 for h in range(6500)] for i in range(w + 1)] for j in range(h + 1)]\nfield[0][0][abs(red[0][0] - blue[0][0])] = 1\nfor i in range(h):\n\tfor j in range(w):\n\t\tfor f in range(6401):\n\t\t\tif field[i][j][f] == 1:\n\t\t\t\tfield[i][j + 1][f + abs(red[i][j + 1] - blue[i][j + 1])] = 1\n\t\t\t\tfield[i][j + 1][abs(f - abs(red[i][j + 1] - blue[i][j + 1]))] = 1\n\t\t\t\tfield[i + 1][j][f + abs(red[i + 1][j] - blue[i + 1][j])] = 1\n\t\t\t\tfield[i + 1][j][abs(f - abs(red[i + 1][j] - blue[i + 1][j]))] = 1\nfor i in range(6500):\n\tif field[h - 1][w - 1][i] == 1:\n\t\tprint(i)\n\t\texit()\n", "def ints():\n\treturn list(map(int, input().split()))\n(H, W) = ints()\nA = [ints() for i in range(H)]\nB = [ints() for i in range(H)]\nC = 20000\ndp = [[0 for j in range(W)] for i in range(H)]\ndp[0][0] |= 1 << C - A[0][0] + B[0][0]\ndp[0][0] |= 1 << C + A[0][0] - B[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i + 1 < H:\n\t\t\tdp[i + 1][j] |= dp[i][j] << abs(A[i + 1][j] - B[i + 1][j])\n\t\t\tdp[i + 1][j] |= dp[i][j] >> abs(A[i + 1][j] - B[i + 1][j])\n\t\tif j + 1 < W:\n\t\t\tdp[i][j + 1] |= dp[i][j] << abs(A[i][j + 1] - B[i][j + 1])\n\t\t\tdp[i][j + 1] |= dp[i][j] >> abs(A[i][j + 1] - B[i][j + 1])\nans = 10 ** 100\nfor k in range(2 * C):\n\tif dp[H - 1][W - 1] >> k & 1:\n\t\tans = min(ans, abs(k - C))\nprint(ans)\n", "I = [int(_) for _ in open(0).read().split()]\n(H, W) = I[:2]\nA = I[2:2 + H * W]\nB = I[2 + H * W:]\nD = [abs(a - b) for (a, b) in zip(A, B)]\ndp = [set([])] + [set([0])] + [set([])] * (W - 1)\nfor h in range(H):\n\tdpo = dp\n\tdp = [set([])] + [None] * W\n\tfor (w, d) in enumerate(D[W * h:W * (h + 1)]):\n\t\ts = dp[w] | dpo[w + 1]\n\t\tdp[w + 1] = {v + d for v in s} | {abs(v - d) for v in s}\nprint(min(dp[-1]))\n", "def main():\n\timport sys\n\tinput = sys.stdin.readline\n\tsys.setrecursionlimit(10 ** 7)\n\tfrom collections import Counter, deque\n\tfrom itertools import combinations, permutations, accumulate, groupby, product\n\tfrom bisect import bisect_left, bisect_right\n\tfrom heapq import heapify, heappop, heappush\n\timport math\n\t(h, w) = map(int, input().split())\n\ta = [list(map(int, input().split())) for _ in range(h)]\n\tb = [list(map(int, input().split())) for _ in range(h)]\n\tc = [[0] * w for _ in range(h)]\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tc[i][j] = abs(a[i][j] - b[i][j])\n\tmid = 6400\n\tdp = [[0] * w for _ in range(h)]\n\tdp[0][0] = 1 << mid + c[0][0] | 1 << mid - c[0][0]\n\tfor x in range(h):\n\t\tfor y in range(w):\n\t\t\tfor (dx, dy) in [[0, 1], [1, 0]]:\n\t\t\t\tnx = x + dx\n\t\t\t\tny = y + dy\n\t\t\t\tif 0 <= nx < h and 0 <= ny < w:\n\t\t\t\t\tdp[nx][ny] = dp[nx][ny] | dp[x][y] << c[nx][ny]\n\t\t\t\t\tdp[nx][ny] = dp[nx][ny] | dp[x][y] >> c[nx][ny]\n\tfor i in range(mid + 1):\n\t\tif dp[-1][-1] & 1:\n\t\t\tres = mid - i\n\t\tdp[-1][-1] >>= 1\n\tprint(res)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(H, W) = list(map(int, input().split()))\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\ndp = [[0] * W for i in range(H)]\ndp[0][0] = 1 << abs(A[0][0] - B[0][0]) + 6400\nfor i in range(H):\n\tfor j in range(W):\n\t\td = abs(A[i][j] - B[i][j])\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << d | dp[i - 1][j] >> d\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << d | dp[i][j - 1] >> d\nans = 0\nres = dp[H - 1][W - 1] >> 6400\nwhile res & 1 == 0:\n\tres >>= 1\n\tans += 1\nprint(ans)\n", "import sys\ninput = sys.stdin.readline\n(H, W) = map(int, input().split())\ndiff = [list(map(int, input().split())) for _ in range(H)]\nfor i in range(H):\n\tB = list(map(int, input().split()))\n\tfor j in range(W):\n\t\tdiff[i][j] = abs(diff[i][j] - B[j])\ndp = [[False] * W for _ in range(H)]\nofs = 80 * (H + W)\ndp[0][0] = 1 << ofs + diff[0][0] | 1 >> ofs - diff[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << diff[i][j] | dp[i - 1][j] >> diff[i][j]\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << diff[i][j] | dp[i][j - 1] >> diff[i][j]\nfor k in range(ofs):\n\tif dp[-1][-1] >> k + ofs & 1:\n\t\tprint(k)\n\t\tbreak\n", "(H, W) = list(map(int, input().split()))\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nZ = (H + W) * 80 + 10\ndp = [[0] * (W + 1) for _ in range(H + 1)]\ndp[0][0] = 1 << Z\nfor h in range(H):\n\tfor w in range(W):\n\t\td = dp[h][w]\n\t\tk = abs(A[h][w] - B[h][w])\n\t\tdp[h + 1][w] |= d << k | d >> k\n\t\tdp[h][w + 1] |= d << k | d >> k\nans = 10 ** 18\nfor a in (dp[H][W - 1], dp[H - 1][W]):\n\tfor d in range(Z * 2 + 10):\n\t\tif a & 1 << d != 0:\n\t\t\tans = min(ans, abs(d - Z))\nprint(ans)\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\nd = [[a[i][j] - b[i][j] for j in range(w)] for i in range(h)]\ndp = [w * [0] for _ in range(h)]\ndp[0][0] = 1 << 80 + d[0][0] | 1 << 80 - d[0][0]\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i != 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << 80 + d[i][j]\n\t\t\tdp[i][j] |= dp[i - 1][j] << 80 - d[i][j]\n\t\tif j != 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << 80 + d[i][j]\n\t\t\tdp[i][j] |= dp[i][j - 1] << 80 - d[i][j]\nn = dp[-1][-1] | 1 << 15000\nans = 1 << 1000\nfor i in range(15000):\n\tif n & 1 << i:\n\t\tans = min(ans, abs(i - (h + w - 1) * 80))\nprint(ans)\n", "import sys\ninput = sys.stdin.readline\n\ndef main():\n\t(h, w) = map(int, input().split())\n\tred = [[int(x) for x in input().split()] for _ in range(h)]\n\tblue = [[int(x) for x in input().split()] for _ in range(h)]\n\tmax_dp = 13000\n\tdp_first = 2 ** max_dp\n\tdp = [[0] * (w + 1) for _ in range(h + 1)]\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tsub = dp[i][j + 1] | dp[i + 1][j]\n\t\t\tsub = sub | dp_first if i == j == 0 else sub\n\t\t\tshift = abs(red[i][j] - blue[i][j])\n\t\t\tdp[i + 1][j + 1] = sub << shift | sub >> shift\n\tjudge = dp[h][w]\n\tfor i in range(max_dp):\n\t\tif judge >> max_dp + i & 1 or judge >> max_dp - i & 1:\n\t\t\tprint(i)\n\t\t\treturn\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(n, m) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(n)]\nb = [list(map(int, input().split())) for _ in range(n)]\ndp = [[0 for _ in range(m)] for _ in range(n)]\ndp[0][0] = 1 << a[0][0] - b[0][0] + 12880 | 1 << b[0][0] - a[0][0] + 12880\nmxs = (1 << 12880 * 2 + 1) - 1\nfor i in range(n):\n\tfor j in range(m):\n\t\tif not i and (not j):\n\t\t\tcontinue\n\t\td = abs(a[i][j] - b[i][j])\n\t\tif i:\n\t\t\tu = dp[i - 1][j] << d & mxs\n\t\t\tv = dp[i - 1][j] >> d\n\t\t\tdp[i][j] |= u\n\t\t\tdp[i][j] |= v\n\t\tif j:\n\t\t\tu = dp[i][j - 1] << d & mxs\n\t\t\tv = dp[i][j - 1] >> d & mxs\n\t\t\tdp[i][j] |= u\n\t\t\tdp[i][j] |= v\nc = dp[n - 1][m - 1] >> 12880\nfor i in range(12880):\n\tif c & 1:\n\t\tprint(i)\n\t\tbreak\n\tc >>= 1\n", "import math\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\ndiff = [[abs(x - y) for (x, y) in zip(ar, br)] for (ar, br) in zip(a, b)]\nM = 80 * (h + w)\ndp = [[0 for j in range(w)] for i in range(h)]\ndp[0][0] = 1 << diff[0][0] + M\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << diff[i][j] | dp[i - 1][j] >> diff[i][j]\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << diff[i][j] | dp[i][j - 1] >> diff[i][j]\n\t\tdp[i][j] &= (1 << M * 2) - 1\nfor k in range(M):\n\tif dp[h - 1][w - 1] >> k + M & 1 == 1:\n\t\tprint(k)\n\t\tbreak\n", "(h, w) = map(int, input().split())\nab = []\nfor i in range(h * 2):\n\tab.extend(list(map(int, input().split())))\nabs_table = [[0] * w for _ in range(h)]\ndp = [[0] * w for _ in range(h)]\ns = h * w\ni = 0\nj = 0\nfor k in range(s):\n\tif w == j:\n\t\tj = 0\n\t\ti += 1\n\t(a, b) = (ab[k], ab[k + s])\n\tabs_table[i][j] = abs(a - b)\n\tj += 1\nn = abs_table[0][0]\ndp[0][0] = 2 ** (n * 2) | 1\nfor i in range(h):\n\tfor j in range(w):\n\t\ta = abs_table[i][j]\n\t\tu = 0\n\t\tl = 0\n\t\tif i:\n\t\t\tu = dp[i - 1][j]\n\t\t\tu = u << a * 2 | u | u\n\t\tif j:\n\t\t\tl = dp[i][j - 1]\n\t\t\tl = l << a * 2 | l | l\n\t\tif not u and (not l):\n\t\t\tpass\n\t\telif not l:\n\t\t\tdp[i][j] = u\n\t\telif not u:\n\t\t\tdp[i][j] = l\n\t\telse:\n\t\t\tlen_u = len(bin(u)[2:])\n\t\t\tlen_l = len(bin(l)[2:])\n\t\t\tdelta = len_u - len_l\n\t\t\tif delta == 0:\n\t\t\t\tdp[i][j] = u | l\n\t\t\telif delta < 0:\n\t\t\t\tdp[i][j] = u << abs(delta) // 2 | l\n\t\t\telse:\n\t\t\t\tdp[i][j] = u | l << delta // 2\nflag = bin(dp[-1][-1])[2:]\nzero = len(flag) // 2\nfor (i, v) in enumerate(flag[zero:]):\n\tif v == '1':\n\t\tprint(i)\n\t\tbreak\n", "import sys\ninput = sys.stdin.readline\n\ndef main():\n\t(h, w) = map(int, input().split())\n\tA = [list(map(int, input().split())) for _ in range(h)]\n\tB = [list(map(int, input().split())) for _ in range(h)]\n\tM = 80 * (h + w)\n\tdp = [[0] * w for i in range(h)]\n\td = abs(A[0][0] - B[0][0])\n\tmask = (1 << 2 * M) - 1\n\tdp[0][0] |= 1 << M - d\n\tdp[0][0] |= 1 << M + d\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\td = abs(A[i][j] - B[i][j])\n\t\t\tif i:\n\t\t\t\tdp[i][j] |= dp[i - 1][j] << d & mask\n\t\t\t\tdp[i][j] |= dp[i - 1][j] >> d\n\t\t\tif j:\n\t\t\t\tdp[i][j] |= dp[i][j - 1] << d & mask\n\t\t\t\tdp[i][j] |= dp[i][j - 1] >> d\n\tt = dp[-1][-1] >> M\n\tans = (t & -t).bit_length() - 1\n\tprint(ans)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "import sys\ninput = sys.stdin.readline\n(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nSA = [[0] * W for i in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tSA[i][j] = abs(A[i][j] - B[i][j])\nDP = [[0 for i in range(W)] for j in range(H)]\nDP[0][0] = 1 << (H + W) * 80 + SA[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\ttempbit = DP[i][j]\n\t\tif i + 1 < H:\n\t\t\tDP[i + 1][j] |= tempbit << SA[i + 1][j]\n\t\t\tDP[i + 1][j] |= tempbit >> SA[i + 1][j]\n\t\tif j + 1 < W:\n\t\t\tDP[i][j + 1] |= tempbit << SA[i][j + 1]\n\t\t\tDP[i][j + 1] |= tempbit >> SA[i][j + 1]\nANS = 1 << 30\nfor i in range((H + W) * 160 + 1):\n\tif 1 << i & DP[-1][-1] != 0:\n\t\tANS = min(ANS, abs(i - (H + W) * 80))\nprint(ANS)\n", "import sys\nsys.setrecursionlimit(2147483647)\nINF = float('inf')\nMOD = 10 ** 9 + 7\ninput = lambda : sys.stdin.readline().rstrip()\n\ndef resolve():\n\t(h, w) = map(int, input().split())\n\tA = [list(map(int, input().split())) for _ in range(h)]\n\tB = [list(map(int, input().split())) for _ in range(h)]\n\td = abs(A[0][0] - B[0][0])\n\tofs = 12800\n\tdp = [[0] * w for _ in range(h)]\n\tdp[0][0] = 1 << ofs + d | 1 << ofs - d\n\tfrom itertools import product\n\tfor (i, j) in product(range(h), range(w)):\n\t\tif i == 0 and j == 0:\n\t\t\tcontinue\n\t\td = abs(A[i][j] - B[i][j])\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << d | dp[i - 1][j] >> d\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << d | dp[i][j - 1] >> d\n\tfor i in range(ofs):\n\t\tif dp[-1][-1] >> i + ofs & 1:\n\t\t\tprint(i)\n\t\t\treturn\nresolve()\n", "(h, w) = map(int, input().split())\nA = [[0] * w for i in range(h)]\nfor i in range(h):\n\tA[i] = list(map(int, input().split()))\nB = [[0] * w for i in range(h)]\nfor i in range(h):\n\tB[i] = list(map(int, input().split()))\nC = [[0] * w for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\ndp = [[[0] * 6401 for j in range(h + 1)] for i in range(h + w + 1)]\ndp[0][0][C[0][0]] = 1\nfor i in range(h + w):\n\tfor j in range(max(0, i - w), min(i, h) + 1):\n\t\tfor k in range(6401):\n\t\t\tif dp[i][j][k] == 1:\n\t\t\t\tif i - j < w - 1:\n\t\t\t\t\tif k + C[j][i - j + 1] < 6400:\n\t\t\t\t\t\tdp[i + 1][j][k + C[j][i - j + 1]] = 1\n\t\t\t\t\tdp[i + 1][j][abs(k - C[j][i - j + 1])] = 1\n\t\t\t\tif j < h - 1:\n\t\t\t\t\tif k + C[j + 1][i - j] < 6400:\n\t\t\t\t\t\tdp[i + 1][j + 1][k + C[j + 1][i - j]] = 1\n\t\t\t\t\tdp[i + 1][j + 1][abs(k - C[j + 1][i - j])] = 1\nfor k in range(6400):\n\tif dp[h + w - 2][h - 1][k] == 1:\n\t\tprint(k)\n\t\texit()\n", "(h, w) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(h)]\nB = [list(map(int, input().split())) for i in range(h)]\nC = [[0] * w for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\ndp = [[0] * w for i in range(h)]\nm = 80\ndp[0][0] = 1 << m + C[0][0] | 1 << m - C[0][0]\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i >= 1:\n\t\t\tdp[i][j] |= dp[i - 1][j] << m + C[i][j] | dp[i - 1][j] << m - C[i][j]\n\t\tif j >= 1:\n\t\t\tdp[i][j] |= dp[i][j - 1] << m + C[i][j] | dp[i][j - 1] << m - C[i][j]\nb = list(bin(dp[h - 1][w - 1]))[::-1]\nans = float('inf')\nfor i in range(len(b)):\n\tif b[i] == '1':\n\t\tans = min(ans, abs(m * (h + w - 1) - i))\nprint(ans)\n", "(H, W) = list(map(int, input().split()))\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nM = 6401\n\ndef honya(y, d):\n\tt = (1 << d + 1) - 1\n\tt = y & t\n\tk = 0\n\tfor i in range(d):\n\t\tk += t & 1\n\t\tt >>= 1\n\t\tk <<= 1\n\treturn k\nD = [[0] * W for _ in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tD[i][j] = abs(B[i][j] - A[i][j])\nDP = [[0] * W for _ in range(H)]\n\ndef nasu(x, y, d):\n\tt = (1 << d + 1) - 1 & y\n\treturn (x | y << d | y >> d | honya(y, d)) & mask\nmask = (1 << M) - 1\nDP[0][0] = 1 << D[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i + 1 < H:\n\t\t\tDP[i + 1][j] = nasu(DP[i + 1][j], DP[i][j], D[i + 1][j])\n\t\tif j + 1 < W:\n\t\t\tDP[i][j + 1] = nasu(DP[i][j + 1], DP[i][j], D[i][j + 1])\nt = DP[-1][-1]\nfor i in range(M):\n\tif t & 1:\n\t\tprint(i)\n\t\tbreak\n\tt >>= 1\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\nd = [[0 for j in range(w)] for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\td[i][j] = abs(a[i][j] - b[i][j])\ndp = [[0 for _ in range(6400)] for _ in range(h * w)]\ndp[0][d[0][0]] = 1\nfor i in range(h * w):\n\t(nowh, noww) = divmod(i, w)\n\tfor k in range(6400):\n\t\tif not dp[nowh * w + noww][k] == 1:\n\t\t\tcontinue\n\t\t(nxth, nxtw) = (nowh + 1, noww + 1)\n\t\tif nxtw < w:\n\t\t\tif k + d[nowh][nxtw] < 6400:\n\t\t\t\tdp[nowh * w + nxtw][k + d[nowh][nxtw]] = 1\n\t\t\tdp[nowh * w + nxtw][abs(k - d[nowh][nxtw])] = 1\n\t\tif nxth < h:\n\t\t\tif k + d[nxth][noww] < 6400:\n\t\t\t\tdp[nxth * w + noww][k + d[nxth][noww]] = 1\n\t\t\tdp[nxth * w + noww][abs(k - d[nxth][noww])] = 1\nfor k in range(6400):\n\tif dp[-1][k] == 1:\n\t\tprint(k)\n\t\texit()\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nC = [[0 for j in range(W)] for i in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\ndp = [[0 for k in range(6400)] for g in range(H * W)]\ndp[0][C[0][0]] = 1\nfor g in range(H * W):\n\t(i, j) = divmod(g, W)\n\tfor k in range(6400):\n\t\tif not dp[i * W + j][k]:\n\t\t\tcontinue\n\t\t(ni, nj) = (i + 1, j + 1)\n\t\tif ni < H:\n\t\t\tif k + C[ni][j] < 6400:\n\t\t\t\tdp[ni * W + j][k + C[ni][j]] = 1\n\t\t\tdp[ni * W + j][abs(k - C[ni][j])] = 1\n\t\tif nj < W:\n\t\t\tif k + C[i][nj] < 6400:\n\t\t\t\tdp[i * W + nj][k + C[i][nj]] = 1\n\t\t\tdp[i * W + nj][abs(k - C[i][nj])] = 1\nfor k in range(6400):\n\tif dp[-1][k]:\n\t\tprint(k)\n\t\tbreak\n", "(h, w) = map(int, input().split())\narr = [list(map(int, input().split())) for _ in range(2 * h)]\nboard = [[0] * w for _ in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tboard[i][j] += arr[i][j]\nfor i in range(h):\n\tfor j in range(w):\n\t\tboard[i][j] = abs(board[i][j] - arr[h + i][j])\ndp = [[set() for _ in range(w)] for _ in range(h)]\ndp[0][0].add(board[0][0])\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i != 0:\n\t\t\tfor k in dp[i - 1][j]:\n\t\t\t\tdp[i][j].add((k + board[i][j]) % 640)\n\t\t\t\tdp[i][j].add(abs(k - board[i][j]) % 640)\n\t\tif j != 0:\n\t\t\tfor k in dp[i][j - 1]:\n\t\t\t\tdp[i][j].add((k + board[i][j]) % 640)\n\t\t\t\tdp[i][j].add(abs(k - board[i][j]) % 640)\nprint(min(dp[h - 1][w - 1]))\n", "tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]\n(h, w) = list(map(int, input().split()))\nD = 160 * 80\nD2 = D * 2 + 1\ndiff = [list(map(int, input().split())) for _ in range(h)]\nfor i in range(h):\n\tfor (j, b) in enumerate(list(map(int, input().split()))):\n\t\tdiff[i][j] = abs(diff[i][j] - b)\ndp = tdlist(h, w)\ndp[0][0] |= 1 << D + diff[0][0]\ndp[0][0] |= 1 << D - diff[0][0]\nfor i in range(h):\n\tfor j in range(w):\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << diff[i][j]\n\t\t\tdp[i][j] |= dp[i][j - 1] >> diff[i][j]\n\t\tif i:\n\t\t\tdp[i][j] |= dp[i - 1][j] << diff[i][j]\n\t\t\tdp[i][j] |= dp[i - 1][j] >> diff[i][j]\nans = float('inf')\nfor i in range(D2):\n\tif dp[h - 1][w - 1] >> i & 1:\n\t\tans = min(ans, abs(i - D))\nprint(ans)\n", "import sys\ninput = sys.stdin.readline\n(H, W) = map(int, input().split())\n(A, B) = ([None] * H, [None] * H)\nfor i in range(H):\n\tA[i] = list(map(int, input().split()))\nfor i in range(H):\n\tB[i] = list(map(int, input().split()))\nC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\nM = 80 * (80 + 80)\ndp = [[0 for j in range(W + 1)] for i in range(H + 1)]\ndp[0][1] = 1\ndp[1][0] = 1\nfor i in range(1, H + 1):\n\tfor j in range(1, W + 1):\n\t\td = C[i - 1][j - 1]\n\t\tif d != 0:\n\t\t\tx = int(bin((dp[i - 1][j] & 2 ** d - 1) + 2 ** d)[::-1][:d], 2) << 1\n\t\t\ty = int(bin((dp[i][j - 1] & 2 ** d - 1) + 2 ** d)[::-1][:d], 2) << 1\n\t\telse:\n\t\t\tx = y = 0\n\t\tdp[i][j] = dp[i - 1][j] >> d | dp[i - 1][j] << d | dp[i][j - 1] >> d | dp[i][j - 1] << d | x | y\nfor (i, v) in enumerate(bin(dp[H][W])[::-1]):\n\tif v == '1':\n\t\tprint(i)\n\t\tbreak\n", "import sys\ninput = sys.stdin.readline\n(h, w) = map(int, input().split())\nA = []\nfor i in range(h):\n\tline = list(map(int, input().split()))\n\tA.append(line)\nfor i in range(h):\n\tline = list(map(int, input().split()))\n\tfor (j, num) in enumerate(line):\n\t\tA[i][j] = abs(A[i][j] - num)\nconst = 64000\nbitset = 1 << const\nDP = [0] * w\nDP[0] = bitset >> A[0][0]\n\ndef slide_down(y, x):\n\tbit = DP[x]\n\tdelta = A[y + 1][x]\n\tnew1 = bit << delta\n\tnew2 = bit >> delta\n\tDP[x] = new1 | new2\n\ndef slide_right(y, x):\n\tbit = DP[x]\n\tdelta = A[y][x + 1]\n\tnew1 = bit << delta\n\tnew2 = bit >> delta\n\tDP[x + 1] |= new1 | new2\nfor y in range(h):\n\tfor x in range(w):\n\t\tif x < w - 1:\n\t\t\tslide_right(y, x)\n\t\tif y < h - 1:\n\t\t\tslide_down(y, x)\nans = DP[w - 1]\nfor i in range(81):\n\tif ans >> const + i & 1 or ans >> const - i & 1:\n\t\tprint(i)\n\t\texit()\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\ndp = [[0] * (w + 1) for i in range(h + 1)]\ndp[0][0] = 1 << (h + w) * 80\nfor i in range(h):\n\tfor j in range(w):\n\t\tdiff = abs(a[i][j] - b[i][j])\n\t\tdp[i + 1][j] |= dp[i][j] << diff | dp[i][j] >> diff\n\t\tdp[i][j + 1] |= dp[i][j] << diff | dp[i][j] >> diff\nans = float('inf')\nfor i in range((h + w) * 160):\n\tif dp[h][w - 1] & 1 << i:\n\t\tans = min(ans, abs(i - (h + w) * 80))\nprint(ans)\n", "def p_e():\n\t(h, w) = map(int, input().split())\n\tt1 = [list(map(int, input().split())) for _ in range(h)]\n\tt2 = [list(map(int, input().split())) for _ in range(h)]\n\tm = 160 * 80\n\tdp = [[0] * w for _ in range(h)]\n\tdp[0][0] = 1 << m\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tv = abs(t1[i][j] - t2[i][j])\n\t\t\tif i > 0:\n\t\t\t\tdp[i][j] |= dp[i - 1][j]\n\t\t\tif j > 0:\n\t\t\t\tdp[i][j] |= dp[i][j - 1]\n\t\t\tdp[i][j] = dp[i][j] << v | dp[i][j] >> v\n\tans = m\n\tfor i in range(m * 2):\n\t\tif dp[h - 1][w - 1] & 1 << i > 0:\n\t\t\tans = min(ans, abs(m - i))\n\tprint(ans)\np_e()\n", "import sys\ninput = sys.stdin.buffer.readline\n(h, w) = map(int, input().split())\na = [map(int, input().split()) for _ in range(h)]\nb = [map(int, input().split()) for _ in range(h)]\ng = [list((abs(x - y) for (x, y) in zip(l1, l2))) for (l1, l2) in zip(a, b)]\nposs = [[0] * w for _ in range(h)]\nposs[0][0] |= 1 << 6400 + g[0][0]\nposs[0][0] |= 1 << 6400 - g[0][0]\nfor i in range(h):\n\tfor j in range(w - 1):\n\t\tposs[i][j + 1] |= poss[i][j] << g[i][j + 1]\n\t\tposs[i][j + 1] |= poss[i][j] >> g[i][j + 1]\n\tif i != h - 1:\n\t\tfor j in range(w):\n\t\t\tposs[i + 1][j] |= poss[i][j] << g[i + 1][j]\n\t\t\tposs[i + 1][j] |= poss[i][j] >> g[i + 1][j]\nres = poss[-1][-1]\nfor i in range(6400):\n\tif res & 1 << 6400 + i or res & 1 << 6400 - i:\n\t\tprint(i)\n\t\texit()\n", "def fold(x, m):\n\ty = 0\n\tfor _ in range(m):\n\t\ty |= x & 1\n\t\ty <<= 1\n\t\tx >>= 1\n\treturn x | y\nlmi = lambda : list(map(int, input().split()))\n(h, w) = lmi()\na = [lmi() for _ in range(2 * h)]\ng = [[abs(a[i][j] - a[i + h][j]) for j in range(w)] for i in range(h)]\nmask = (1 << 12801) - 1\ndp = [[0] * (w + 1) for _ in range(h + 1)]\ndp[0][0] = 1\nfor i in range(h):\n\tfor j in range(w):\n\t\t(cur, par) = (g[i][j], dp[i][j])\n\t\tpos = par << cur | fold(par, cur)\n\t\tpos &= mask\n\t\tdp[i + 1][j] |= pos\n\t\tdp[i][j + 1] |= pos\nfor i in range(12801):\n\tif dp[-1][-2] & 1 << i:\n\t\tprint(i)\n\t\tbreak\n", "maxV = 80 * (80 + 80)\n(H, W) = list(map(int, input().split()))\nAss = [tuple(map(int, input().split())) for _ in range(H)]\nBss = [tuple(map(int, input().split())) for _ in range(H)]\ndp = [[0 for j in range(W)] for i in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\t(A, B) = (Ass[i][j], Bss[i][j])\n\t\tif A > B:\n\t\t\t(A, B) = (B, A)\n\t\tif i == 0 and j == 0:\n\t\t\tdp[i][j] = 1 << maxV + B - A | 1 << maxV - B + A\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << B - A | dp[i - 1][j] >> B - A\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << B - A | dp[i][j - 1] >> B - A\nbitset = dp[-1][-1]\nmask = 1 << 2 * maxV\nans = maxV\nfor i in range(-maxV, maxV + 1):\n\tif bitset & mask:\n\t\tans = min(ans, abs(i))\n\tmask >>= 1\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = [[int(a) for a in input().split()] for _ in range(H)]\nB = [[int(b) for b in input().split()] for _ in range(H)]\nC = [[0] * W for _ in range(H)]\nnum = 80\nfor i in range(H):\n\tfor j in range(W):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\ndp = [[0] * W for _ in range(H)]\ndp[0][0] |= 1 << num + C[0][0] | 1 << num - C[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << num + C[i][j] | dp[i - 1][j] << num - C[i][j]\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << num + C[i][j] | dp[i][j - 1] << num - C[i][j]\nb = list(bin(dp[-1][-1]))[::-1]\nans = 10 ** 9\nfor i in range(len(b)):\n\tif b[i] == '1':\n\t\tans = min(ans, abs(num * (H + W - 1) - i))\nprint(ans)\n", "import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools\nimport time, random\nsys.setrecursionlimit(10 ** 7)\ninf = 10 ** 20\neps = 1.0 / 10 ** 10\nmod = 10 ** 9 + 7\nmod2 = 998244353\ndd = [(-1, 0), (0, 1), (1, 0), (0, -1)]\nddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI():\n\treturn [list(map(int, l.split())) for l in sys.stdin.readlines()]\n\ndef LI_():\n\treturn [int(x) - 1 for x in sys.stdin.readline().split()]\n\ndef LF():\n\treturn [float(x) for x in sys.stdin.readline().split()]\n\ndef LS():\n\treturn sys.stdin.readline().split()\n\ndef I():\n\treturn int(sys.stdin.readline())\n\ndef F():\n\treturn float(sys.stdin.readline())\n\ndef S():\n\treturn input()\n\ndef pf(s):\n\treturn print(s, flush=True)\n\ndef pe(s):\n\treturn print(str(s), file=sys.stderr)\n\ndef JA(a, sep):\n\treturn sep.join(map(str, a))\n\ndef JAA(a, s, t):\n\treturn s.join((t.join(map(str, b)) for b in a))\n\ndef main():\n\t(h, w) = LI()\n\ta = [LI() for _ in range(h)]\n\tb = [LI() for _ in range(h)]\n\tm = 1 << 80 * 80 * 2 + 3\n\tr = [[0] * w for _ in range(h)]\n\tc = abs(a[0][0] - b[0][0])\n\tr[0][0] |= 1 << 80 * 80 + 1 << c\n\tr[0][0] |= 1 << 80 * 80 + 1 >> c\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tif i == 0 and j == 0:\n\t\t\t\tcontinue\n\t\t\tc = abs(a[i][j] - b[i][j])\n\t\t\tt = 0\n\t\t\tif i > 0:\n\t\t\t\tt |= (r[i - 1][j] << c) % m\n\t\t\t\tt |= r[i - 1][j] >> c\n\t\t\tif j > 0:\n\t\t\t\tt |= (r[i][j - 1] << c) % m\n\t\t\t\tt |= r[i][j - 1] >> c\n\t\t\tr[i][j] = t\n\tc = r[-1][-1]\n\tt = 10000\n\tfor i in range(80 * 80 * 2 + 3):\n\t\tif 1 << i & c > 0:\n\t\t\tk = abs(i - (80 * 80 + 1))\n\t\t\tif t > k:\n\t\t\t\tt = k\n\treturn t\nprint(main())\n", "import numpy as np\n(h, w) = map(int, input().split())\nA = [0] * h\nB = [0] * h\nfor _ in range(h):\n\tA[_] = list(map(int, input().split()))\nfor _ in range(h):\n\tB[_] = list(map(int, input().split()))\nC = [[0] * w for _ in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\ndp = [[0] * w for _ in range(h)]\nD = 80 * (h + w)\nL = 2 * D + 1\ndp[0][0] = np.zeros(L, np.bool)\ndp[0][0][D + C[0][0]] = 1\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i == 0 and j == 0:\n\t\t\tcontinue\n\t\tx = np.zeros(L, np.bool)\n\t\tif i != 0:\n\t\t\tx[C[i][j]:] |= dp[i - 1][j][:L - C[i][j]]\n\t\t\tx[:L - C[i][j]] |= dp[i - 1][j][C[i][j]:]\n\t\tif j != 0:\n\t\t\tx[C[i][j]:] |= dp[i][j - 1][:L - C[i][j]]\n\t\t\tx[:L - C[i][j]] |= dp[i][j - 1][C[i][j]:]\n\t\tdp[i][j] = x\ntemp = np.where(dp[-1][-1] > 0)[0] - D\ntemp = np.abs(temp)\nprint(np.min(temp))\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nC = [[] for i in range(H)]\nfor (i, (arow, brow)) in enumerate(zip(A, B)):\n\tfor (a, b) in zip(arow, brow):\n\t\td = abs(a - b)\n\t\tC[i].append(d)\nofs = (H + W) * 100\ndp = [0] * W\ndp[0] = 1 << ofs\nfor (i, crow) in enumerate(C):\n\tdp2 = [0] * W\n\tfor (j, (c, d)) in enumerate(zip(C[i], dp)):\n\t\tdp2[j] |= d << c\n\t\tdp2[j] |= d >> c\n\tfor (j, c) in enumerate(C[i]):\n\t\tif j == 0:\n\t\t\tcontinue\n\t\tdp2[j] |= dp2[j - 1] << c\n\t\tdp2[j] |= dp2[j - 1] >> c\n\tdp = dp2\nans = ofs\nl = len(bin(dp[-1]))\nfor i in range(l):\n\tif dp[-1] & 1 << i:\n\t\tans = min(ans, abs(i - ofs))\nprint(ans)\n", "import sys\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\nreadlines = sys.stdin.buffer.readlines\n\ndef resolve():\n\tofs = 6400\n\t(h, w) = map(int, readline().split())\n\tA = [list(map(int, readline().split())) for _ in range(h)]\n\tB = [list(map(int, readline().split())) for _ in range(h)]\n\tdp = [[0] * w for _ in range(h)]\n\tx = abs(A[0][0] - B[0][0])\n\tdp[0][0] |= 1 << ofs + x | 1 << ofs - x\n\tfrom itertools import product\n\tfor (i, j) in product(range(h), range(w)):\n\t\tx = abs(A[i][j] - B[i][j])\n\t\tt = 0\n\t\tif i - 1 >= 0:\n\t\t\tt |= dp[i - 1][j]\n\t\tif j - 1 >= 0:\n\t\t\tt |= dp[i][j - 1]\n\t\tdp[i][j] |= t << x | t >> x\n\tfor (i, s) in enumerate(bin(dp[-1][-1])[-ofs - 1:]):\n\t\tif s == '1':\n\t\t\tprint(i)\n\t\t\treturn\nINF = float('inf')\nMOD = 10 ** 9 + 7\nresolve()\n", "def ints():\n\treturn [int(x) for x in input().split()]\n\ndef readi():\n\treturn int(input())\n(H, W) = ints()\nA = [ints() for _ in range(H)]\nB = [ints() for _ in range(H)]\nD = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]\nmemo = {}\nmemo = {}\nN = 80 * 60\nmemo[0, 0] = 1 << D[0][0] + N\nfor h in range(H):\n\tfor w in range(W):\n\t\tif h == 0 and w == 0:\n\t\t\tcontinue\n\t\td = D[h][w]\n\t\tf = 0\n\t\tif h > 0:\n\t\t\ts = memo[h - 1, w]\n\t\t\tf |= s << d\n\t\t\tf |= s >> d\n\t\tif w > 0:\n\t\t\ts = memo[h, w - 1]\n\t\t\tf |= s << d\n\t\t\tf |= s >> d\n\t\tmemo[h, w] = f\n\ndef min_keta(n):\n\tb = bin(n >> N)\n\tfor i in range(len(b)):\n\t\tif b[-i - 1] == '1':\n\t\t\treturn i\nprint(min_keta(memo[H - 1, W - 1]))\n", "(h, w) = map(int, input().split())\na = []\nb = []\nfor _ in range(h):\n\ta.append(list(map(int, input().split())))\nfor _ in range(h):\n\tb.append(list(map(int, input().split())))\ngrid = [[0 for _ in range(w)] for _ in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tgrid[i][j] = abs(a[i][j] - b[i][j])\ndp = [[0 for _ in range(80 * (h + w) + 1)] for _ in range(h + w)]\ndp[0][0] = 1\nfor ij in range(h + w - 1):\n\tfor i in range(h):\n\t\tj = ij - i\n\t\tif j < 0 or j >= w:\n\t\t\tcontinue\n\t\tc = grid[i][j]\n\t\tfor k in range(80 * (h + w - 1) + 1):\n\t\t\tif dp[ij][k] == 1:\n\t\t\t\tdp[ij + 1][k + c] = 1\n\t\t\t\tdp[ij + 1][abs(k - c)] = 1\nfor i in range(100):\n\tif dp[-1][i] == 1:\n\t\tprint(i)\n\t\texit()\n", "import sys\ninput = sys.stdin.readline\n\ndef solve():\n\tmaxV = 12800\n\t(H, W) = map(int, input().split())\n\tAss = [tuple(map(int, input().split())) for _ in range(H)]\n\tBss = [tuple(map(int, input().split())) for _ in range(H)]\n\tdp = [[0] * W for _ in range(H)]\n\tdiff = abs(Ass[0][0] - Bss[0][0])\n\tdp0 = 1 << maxV\n\tdp[0][0] = dp0 << diff | dp0 >> diff\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tdiff = abs(Ass[i][j] - Bss[i][j])\n\t\t\tif i > 0:\n\t\t\t\tdp0 = dp[i - 1][j]\n\t\t\t\tdp[i][j] |= dp0 << diff | dp0 >> diff\n\t\t\tif j > 0:\n\t\t\t\tdp0 = dp[i][j - 1]\n\t\t\t\tdp[i][j] |= dp0 << diff | dp0 >> diff\n\tans = maxV\n\tdpHW = dp[-1][-1]\n\tfor i in range(2 * maxV + 1):\n\t\tif dpHW >> i & 1:\n\t\t\tj = abs(i - maxV)\n\t\t\tif j < ans:\n\t\t\t\tans = j\n\tprint(ans)\nsolve()\n", "import sys\n\ndef main():\n\tinput = sys.stdin.readline\n\t(H, W) = map(int, input().split())\n\tA = [list(map(int, input().split())) for _ in range(H)]\n\tB = [list(map(int, input().split())) for _ in range(H)]\n\tmx = 80 * (H + W)\n\tC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\n\tdp = [[0 for _ in range(W)] for __ in range(H)]\n\tdp[0][0] = 1 << mx + C[0][0]\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tfor (ni, nj) in ((i + 1, j), (i, j + 1)):\n\t\t\t\tif ni >= H or nj >= W:\n\t\t\t\t\tcontinue\n\t\t\t\tdp[ni][nj] |= dp[i][j] << C[ni][nj]\n\t\t\t\tdp[ni][nj] |= dp[i][j] >> C[ni][nj]\n\tfor ans in range(mx + 1):\n\t\tif dp[H - 1][W - 1] & (1 << mx + ans | 1 << mx - ans):\n\t\t\tprint(ans)\n\t\t\tbreak\nmain()\n", "import numpy as np\n(H, W) = list(map(int, input().split()))\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nX = (H + W) * 80\nL = X + X + 1\ndp = [[0] * W for _ in range(H)]\nd = abs(A[0][0] - B[0][0])\ndp[0][0] = np.zeros(L, np.bool)\ndp[0][0][X + d] = 1\nfor h in range(H):\n\tfor w in range(W):\n\t\ta = A[h][w]\n\t\tb = B[h][w]\n\t\tif h == w == 0:\n\t\t\tcontinue\n\t\td = abs(a - b)\n\t\tx = np.zeros(L, np.bool)\n\t\tif h != 0:\n\t\t\tx[d:] |= dp[h - 1][w][:L - d]\n\t\t\tx[:L - d] |= dp[h - 1][w][d:]\n\t\tif w != 0:\n\t\t\tx[d:] |= dp[h][w - 1][:L - d]\n\t\t\tx[:L - d] |= dp[h][w - 1][d:]\n\t\tdp[h][w] = x\ndp = dp[-1][-1]\ncan_make = np.where(dp)[0] - X\nanswer = np.abs(can_make).min()\nprint(answer)\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\nc = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]\ndp = [[0] * (13000 * (w + 1)) for _ in range(h + 1)]\ndp[1][0] = 1\ndp[0][13000] = 1\nfor i in range(1, h + 1):\n\tfor j in range(1, w + 1):\n\t\tx = c[i - 1][j - 1]\n\t\tfor k in range(13000):\n\t\t\ty = 0\n\t\t\tif k + x <= 12999:\n\t\t\t\tdp[i][13000 * j + k] |= dp[i - 1][13000 * j + k + x] | dp[i][13000 * (j - 1) + k + x]\n\t\t\tdp[i][13000 * j + k] |= dp[i - 1][13000 * j + abs(k - x)] | dp[i][13000 * (j - 1) + abs(k - x)]\nfor i in range(13000):\n\tif dp[h][13000 * w + i]:\n\t\tans = i\n\t\tprint(ans)\n\t\texit()\n", "import sys\nreadline = sys.stdin.readline\n(H, W) = map(int, readline().split())\nA = [list(map(int, readline().split())) for _ in range(H)]\nB = [list(map(int, readline().split())) for _ in range(H)]\ndp = [[0] * W for _ in range(H)]\nX = (H + W) * 80\nd = abs(A[0][0] - B[0][0])\ndp[0][0] = 1 << X - d\nfor h in range(H):\n\tfor (w, (a, b)) in enumerate(zip(A[h], B[h])):\n\t\tif h == w == 0:\n\t\t\tcontinue\n\t\td = abs(a - b)\n\t\tx = 0\n\t\tif h != 0:\n\t\t\tx |= dp[h - 1][w] << d\n\t\t\tx |= dp[h - 1][w] >> d\n\t\tif w != 0:\n\t\t\tx |= dp[h][w - 1] << d\n\t\t\tx |= dp[h][w - 1] >> d\n\t\tdp[h][w] = x\nbit = bin(dp[-1][-1])[2:]\ncan = [i - X for (i, b) in enumerate(bit[::-1]) if b == '1']\nanswer = min((x if x >= 0 else -x for x in can))\nprint(answer)\n", "def main():\n\t(h, w) = map(int, input().split())\n\ta = [list(map(int, input().split())) for i in range(h)]\n\tb = [list(map(int, input().split())) for i in range(h)]\n\tdp = [[[0] * (80 * (h + w + 1) + 1) for i in range(w)] for j in range(h)]\n\tdp[0][0][abs(a[0][0] - b[0][0])] = 1\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tc = abs(a[i][j] - b[i][j])\n\t\t\tif i != 0 or j != 0:\n\t\t\t\tfor k in range(80 * (i + j + 1) + 1):\n\t\t\t\t\tdp[i][j][k] = dp[i - 1][j][abs(k - c)] | dp[i - 1][j][k + c] | dp[i][j - 1][abs(k - c)] | dp[i][j - 1][k + c]\n\tfor i in range(80 * (h + w + 1) + 1):\n\t\tif dp[h - 1][w - 1][i] == 1:\n\t\t\tprint(i)\n\t\t\tbreak\nmain()\n", "M = 7000\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\ndp = [[0] * (w + 1) for _ in range(h + 1)]\ndp[0][1] = dp[1][0] = 1 << M\nfor i in range(h):\n\tfor j in range(w):\n\t\tdp[i + 1][j + 1] |= dp[i][j + 1] << abs(a[i][j] - b[i][j])\n\t\tdp[i + 1][j + 1] |= dp[i][j + 1] >> abs(a[i][j] - b[i][j])\n\t\tdp[i + 1][j + 1] |= dp[i + 1][j] << abs(a[i][j] - b[i][j])\n\t\tdp[i + 1][j + 1] |= dp[i + 1][j] >> abs(a[i][j] - b[i][j])\nans = M\nfor b in range(2 * M + 1):\n\tif dp[h][w] >> b & 1:\n\t\tans = min(ans, abs(b - M))\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = [None] * H\nfor i in range(H):\n\tA[i] = list(map(int, input().split()))\nB = [None] * H\nfor i in range(H):\n\tB[i] = list(map(int, input().split()))\nC = [[None] * W for _ in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\nK = 80 * (H + W - 1) // 2 + 1\ndp = [[[0] * (K + 1) for _ in range(W)] for _ in range(H)]\ndp[0][0][C[0][0]] = 1\nfor i in range(H):\n\tfor j in range(W):\n\t\tfor k in range(K + 1):\n\t\t\tif i and dp[i - 1][j][k]:\n\t\t\t\tif k + C[i][j] < K:\n\t\t\t\t\tdp[i][j][k + C[i][j]] = 1\n\t\t\t\tdp[i][j][abs(k - C[i][j])] = 1\n\t\t\tif j and dp[i][j - 1][k]:\n\t\t\t\tif k + C[i][j] < K:\n\t\t\t\t\tdp[i][j][k + C[i][j]] = 1\n\t\t\t\tdp[i][j][abs(k - C[i][j])] = 1\nfor k in range(K + 1):\n\tres = dp[H - 1][W - 1][k]\n\tif res:\n\t\tprint(k)\n\t\tbreak\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\nab = [[0] * w for i in range(h)]\nfor ch in range(h):\n\tfor cw in range(w):\n\t\tab[ch][cw] = abs(a[ch][cw] - b[ch][cw])\nab0 = ab[0][0]\nsize = 80 * (h + w)\ndp = [[0] * w for hh in range(h)]\ndp[0][0] |= 2 ** (size + ab0)\ndp[0][0] |= 2 ** (size - ab0)\nfor ch in range(h):\n\tfor cw in range(w):\n\t\tif ch < h - 1:\n\t\t\tdp[ch + 1][cw] |= dp[ch][cw] << ab[ch + 1][cw]\n\t\t\tdp[ch + 1][cw] |= dp[ch][cw] >> ab[ch + 1][cw]\n\t\tif cw < w - 1:\n\t\t\tdp[ch][cw + 1] |= dp[ch][cw] << ab[ch][cw + 1]\n\t\t\tdp[ch][cw + 1] |= dp[ch][cw] >> ab[ch][cw + 1]\na = dp[h - 1][w - 1] >> size\nm = a & -a\nprint(m.bit_length() - 1)\n", "def fold(x, m):\n\ty = 0\n\tfor _ in range(m):\n\t\ty |= x & 1\n\t\ty <<= 1\n\t\tx >>= 1\n\treturn x | y\nlmi = lambda : list(map(int, input().split()))\n(h, w) = lmi()\na = [lmi() for _ in range(2 * h)]\ng = [[abs(a[i][j] - a[i + h][j]) for j in range(w)] for i in range(h)]\nm = 12801\nmask = (1 << m) - 1\na = [0] * (w + 1)\na[0] = 1\nfor i in range(h):\n\tfor j in range(w):\n\t\t(cur, par) = (g[i][j], a[j] | a[j - 1])\n\t\ta[j] = par << cur & mask | fold(par, cur)\nv = a[-2]\nprint((v & -v).bit_length() - 1)\n", "import sys\ninput = sys.stdin.readline\n(h, w) = map(int, input().split())\nA = []\nfor i in range(h):\n\ta_list = list(map(int, input().split()))\n\tA.append(a_list)\nB = []\nfor i in range(h):\n\tb_list = list(map(int, input().split()))\n\tB.append(b_list)\ndp = []\nfor i in range(w):\n\tsub_list = [False] * 12802\n\tdp.append(sub_list)\ndp[0][0] = True\nfor i in range(h):\n\tfor j in range(w):\n\t\tc = A[i][j] - B[i][j]\n\t\tl = [False] * 12802\n\t\tfor x in range(12802):\n\t\t\tif dp[j][x]:\n\t\t\t\tl[abs(x + c)] = True\n\t\t\t\tl[abs(x - c)] = True\n\t\t\t\tif j < w - 1:\n\t\t\t\t\tdp[j + 1][abs(x + c)] = True\n\t\t\t\t\tdp[j + 1][abs(x - c)] = True\n\t\tdp[j] = l\nans = 20000\nfor x in range(12802):\n\tif dp[w - 1][x]:\n\t\tans = min(ans, x)\nprint(ans)\n", "import sys\nread = sys.stdin.buffer.read\ninput = sys.stdin.buffer.readline\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\nab = [[0] * w for i in range(h)]\nfor ch in range(h):\n\tfor cw in range(w):\n\t\tab[ch][cw] = abs(a[ch][cw] - b[ch][cw])\nab0 = ab[0][0]\nsize = 80 * (h + w)\ndp = [[0] * w for hh in range(h)]\ndp[0][0] |= 2 ** (size + ab0)\ndp[0][0] |= 2 ** (size - ab0)\nfor ch in range(h):\n\tfor cw in range(w):\n\t\tif ch < h - 1:\n\t\t\tdp[ch + 1][cw] |= dp[ch][cw] << ab[ch + 1][cw]\n\t\t\tdp[ch + 1][cw] |= dp[ch][cw] >> ab[ch + 1][cw]\n\t\tif cw < w - 1:\n\t\t\tdp[ch][cw + 1] |= dp[ch][cw] << ab[ch][cw + 1]\n\t\t\tdp[ch][cw + 1] |= dp[ch][cw] >> ab[ch][cw + 1]\na = dp[h - 1][w - 1] >> size\nm = a & -a\nprint(m.bit_length() - 1)\n", "import sys\ninput = sys.stdin.readline\n(h, w) = map(int, input().split())\na = [tuple(map(int, input().split())) for _ in range(h)]\nb = [tuple(map(int, input().split())) for _ in range(h)]\nc = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]\nCONST = 80 * 80 * 2 + 100000\ndp = [[0] * w for _ in range(h)]\ndp[0][0] = 1 << c[0][0] + CONST\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i < h - 1:\n\t\t\tdp[i + 1][j] |= dp[i][j] << c[i + 1][j]\n\t\t\tdp[i + 1][j] |= dp[i][j] >> c[i + 1][j]\n\t\tif j < w - 1:\n\t\t\tdp[i][j + 1] |= dp[i][j] << c[i][j + 1]\n\t\t\tdp[i][j + 1] |= dp[i][j] >> c[i][j + 1]\nfor k in range(CONST):\n\tif dp[h - 1][w - 1] & 1 << CONST + k != 0 or dp[h - 1][w - 1] & 1 << CONST - k != 0:\n\t\tans = k\n\t\tbreak\nprint(ans)\n", "import sys\nread = sys.stdin.read\nreadline = sys.stdin.readline\nreadlines = sys.stdin.readlines\n(h, w) = [int(i) for i in readline().split()]\na = [[int(i) for i in readline().split()] for _ in range(h)]\nb = [[int(i) for i in readline().split()] for _ in range(h)]\ndp = [[0] for _ in range(w)]\ndp[0][0] = 1\nN = 6401\nfor i in range(h):\n\tndp = [[0] * N for _ in range(w)]\n\tfor j in range(w):\n\t\tv = abs(a[i][j] - b[i][j])\n\t\tfor (ii, c) in enumerate(dp[j]):\n\t\t\tif ii + v < N:\n\t\t\t\tndp[j][abs(ii + v)] |= c\n\t\t\tndp[j][abs(ii - v)] |= c\n\t\tif j:\n\t\t\tfor (ii, c) in enumerate(ndp[j - 1]):\n\t\t\t\tif ii + v < N:\n\t\t\t\t\tndp[j][abs(ii + v)] |= c\n\t\t\t\tndp[j][abs(ii - v)] |= c\n\tdp = ndp\nc = [i for (i, c) in enumerate(dp[j]) if c]\nprint(min(c))\n", "import sys\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\nwrite = sys.stdout.write\n\ndef solve():\n\tofs = 700\n\t(h, w) = map(int, readline().split())\n\tA = [list(map(int, readline().split())) for i in range(h)]\n\tB = [list(map(int, readline().split())) for i in range(h)]\n\tdp = [0 for _ in range(w + 1)]\n\tx = abs(A[0][0] - B[0][0])\n\tdp[0] = 1 << ofs\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tx = abs(A[i][j] - B[i][j])\n\t\t\tt = dp[j] | dp[j - 1]\n\t\t\tdp[j] = t << x | t >> x\n\tb = list(map(lambda s: s == '1', list(bin(dp[w - 1])[-ofs - 1:-ofs + 100])))\n\tfor (i, s) in enumerate(b):\n\t\tif s:\n\t\t\tprint(i)\n\t\t\treturn\nsolve()\n", "import sys\ninput = sys.stdin.buffer.readline\n(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\nSIZE = 20000\ndp = [[0 for _ in range(W)] for _ in range(H)]\ndp[0][0] = 1 << SIZE + C[0][0] | 1 << SIZE - C[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i == j == 0:\n\t\t\tcontinue\n\t\telse:\n\t\t\tdp[i][j] |= dp[i - 1][j] << C[i][j] | dp[i - 1][j] >> C[i][j]\n\t\t\tdp[i][j] |= dp[i][j - 1] << C[i][j] | dp[i][j - 1] >> C[i][j]\nfor i in range(SIZE):\n\tif dp[-1][-1] >> i + SIZE & 1:\n\t\tprint(i)\n\t\texit()\n", "M = 6400 * 4\nmid = M // 2\nINF = 10 ** 18\n(H, W) = map(int, input().split())\nAs = []\nfor i in range(H):\n\tAs.append(list(map(int, input().split())))\ndiffs = []\nfor i in range(H):\n\tbs = list(map(int, input().split()))\n\tdiffs.append([abs(a - b) for (a, b) in zip(As[i], bs)])\ndp = [[0] * W for j in range(H)]\ndp[0][0] = 1 << mid + diffs[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i + 1 < H:\n\t\t\td = diffs[i + 1][j]\n\t\t\tdp[i + 1][j] |= dp[i][j] >> d\n\t\t\tdp[i + 1][j] |= dp[i][j] << d\n\t\tif j + 1 < W:\n\t\t\td = diffs[i][j + 1]\n\t\t\tdp[i][j + 1] |= dp[i][j] >> d\n\t\t\tdp[i][j + 1] |= dp[i][j] << d\nans = INF\nfor i in range(M):\n\tif dp[H - 1][W - 1] >> i & 1:\n\t\tans = min(ans, abs(i - mid))\nprint(ans)\n", "def run():\n\tofs = 1000\n\t(H, W) = map(int, input().split())\n\tdp = [[0 for w in range(W)] for h in range(H)]\n\ta = [list(map(int, input().split())) for i in range(H)]\n\tb = [list(map(int, input().split())) for i in range(H)]\n\tc = [[abs(a[i][j] - b[i][j]) for j in range(W)] for i in range(H)]\n\tdp[0][0] = 1 << ofs + c[0][0] | 1 << ofs - c[0][0]\n\tfor h in range(1, H):\n\t\tdp[h][0] = dp[h - 1][0] << c[h][0] | dp[h - 1][0] >> c[h][0]\n\tfor w in range(1, W):\n\t\tdp[0][w] = dp[0][w - 1] << c[0][w] | dp[0][w - 1] >> c[0][w]\n\tfor h in range(1, H):\n\t\tfor w in range(1, W):\n\t\t\tv = c[h][w]\n\t\t\tdp[h][w] = dp[h - 1][w] << v | dp[h - 1][w] >> v\n\t\t\tdp[h][w] |= dp[h][w - 1] << v | dp[h][w - 1] >> v\n\ts = list(bin(dp[-1][-1] >> ofs))\n\tfor i in range(len(s)):\n\t\tif s[-1 - i] == '1':\n\t\t\tprint(i)\n\t\t\tbreak\nrun()\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nC = []\nfor (arow, brow) in zip(A, B):\n\tC.append([abs(a - b) for (a, b) in zip(arow, brow)])\nofs = 80 * (H + W)\ndp = [0] * W\ndp[0] = 1 << ofs + C[0][0] | 1 << ofs - C[0][0]\nfor j in range(W - 1):\n\tdp[j + 1] = dp[j] << C[0][j + 1] | dp[j] >> C[0][j + 1]\nfor i in range(1, H):\n\tdp2 = [0] * W\n\tfor j in range(W):\n\t\tdp2[j] = dp[j] << C[i][j] | dp[j] >> C[i][j]\n\t\tif j:\n\t\t\tdp2[j] |= dp2[j - 1] << C[i][j] | dp2[j - 1] >> C[i][j]\n\tdp = dp2\nans = ofs * 2\nfor i in range(ofs * 2):\n\tif dp[-1] & 1 << i:\n\t\tans = min(ans, abs(ofs - i))\nprint(ans)\n", "I = [int(_) for _ in open(0).read().split()]\n(H, W) = I[:2]\nA = I[2:2 + H * W]\nB = I[2 + H * W:]\nD = [abs(a - b) for (a, b) in zip(A, B)]\ndp = [0] + [1] + [0] * (W - 1)\nfor h in range(H):\n\tdpo = dp\n\tdp = [0] * (W + 1)\n\tfor (w, d) in enumerate(D[W * h:W * (h + 1)]):\n\t\ts = dp[w] | dpo[w + 1]\n\t\tdp[w + 1] = s << d | s >> d\n\t\tif d:\n\t\t\tt = bin(s)[2:][::-1][:d + 1]\n\t\t\tt += '0' * (d + 1 - len(t))\n\t\t\tdp[w + 1] |= int(t, 2)\nfor i in range(160 * 80):\n\tif dp[-1] & 2 ** i:\n\t\tprint(i)\n\t\texit()\n", "(h, w) = list(map(int, input().split()))\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\nc = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]\ndp = [[0] * (w + 1) for _ in range(h + 1)]\ndp[0][1] = 1 << 12800\nfor i in range(1, h + 1):\n\tfor j in range(1, w + 1):\n\t\tt = c[i - 1][j - 1]\n\t\tdp[i][j] = dp[i][j - 1] << t | dp[i][j - 1] >> t | dp[i - 1][j] << t | dp[i - 1][j] >> t\nans = 10 ** 20\nfor i in range(25601):\n\tif dp[h][w] & 1 << i:\n\t\tans = min(ans, abs(12800 - i))\nprint(ans)\n", "import sys\nsys.setrecursionlimit(10000000)\nMOD = 10 ** 9 + 7\nINF = 10 ** 15\n\ndef main():\n\t(H, W) = map(int, input().split())\n\tA = [list(map(int, input().split())) for _ in range(H)]\n\tB = [list(map(int, input().split())) for _ in range(H)]\n\tdp = [[0] * (1 + W) for _ in range(H + 1)]\n\tx = abs(A[0][0] - B[0][0])\n\tdp[0][0] = 1 << 12800 + x\n\tdp[0][0] |= 1 << 12800 - x\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tc = abs(A[i][j] - B[i][j])\n\t\t\tif i > 0:\n\t\t\t\tdp[i][j] |= dp[i - 1][j] << c\n\t\t\t\tdp[i][j] |= dp[i - 1][j] >> c\n\t\t\tif j > 0:\n\t\t\t\tdp[i][j] |= dp[i][j - 1] << c\n\t\t\t\tdp[i][j] |= dp[i][j - 1] >> c\n\tans = INF\n\tx = dp[H - 1][W - 1]\n\tfor i in range(25600):\n\t\tif x & 1:\n\t\t\tans = min(ans, abs(i - 12800))\n\t\tx >>= 1\n\tprint(ans)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "import sys\ninput = sys.stdin.readline\n\ndef main():\n\t(H, W) = map(int, input().split())\n\tP = W + 1\n\tA = [list(map(int, input().split())) for _ in range(H)]\n\tB = [list(map(int, input().split())) for _ in range(H)]\n\tL = 80 * 80\n\tdp = [[False] * (L + 1) for _ in range((W + 1) * (H + 1))]\n\tdp[P + 1][abs(A[0][0] - B[0][0])] = True\n\tfor h in range(H):\n\t\tfor w in range(W):\n\t\t\tif h == 0 and w == 0:\n\t\t\t\tcontinue\n\t\t\tc = abs(A[h][w] - B[h][w])\n\t\t\tfor l in range(L - c + 1):\n\t\t\t\tb1 = abs(l - c)\n\t\t\t\tb2 = abs(l + c)\n\t\t\t\tdp[(h + 1) * P + w + 1][l] = dp[h * P + w + 1][b1] or dp[(h + 1) * P + w][b1] or dp[h * P + w + 1][b2] or dp[(h + 1) * P + w][b2]\n\tfor l in range(L + 1):\n\t\tif dp[H * P + W][l]:\n\t\t\tprint(l)\n\t\t\tbreak\nmain()\n", "(h, w) = map(int, input().split())\ndiffs = []\nfor y in range(h):\n\trow = map(int, input().split())\n\tdiffs.append(list(row))\nfor y in range(h):\n\trow = map(int, input().split())\n\tfor (x, b) in zip(range(w), row):\n\t\tdiffs[y][x] = abs(diffs[y][x] - b)\nm = 80 * (h + w)\ndp = [[0 for j in range(w)] for k in range(h)]\nd = m - diffs[0][0]\ndp[0][0] = 1 << d\nfor y in range(h):\n\tfor x in range(w):\n\t\tif x == y == 0:\n\t\t\tcontinue\n\t\tdiff = diffs[y][x]\n\t\tif y != 0:\n\t\t\tdp[y][x] |= dp[y - 1][x] << diff\n\t\t\tdp[y][x] |= dp[y - 1][x] >> diff\n\t\tif x != 0:\n\t\t\tdp[y][x] |= dp[y][x - 1] << diff\n\t\t\tdp[y][x] |= dp[y][x - 1] >> diff\nend = bin(dp[-1][-1])[2:][::-1]\ncandidates = [abs(i - m) for (i, b) in enumerate(end) if b == '1']\nans = min(candidates)\nprint(ans)\n", "import sys\n\ndef main():\n\tinp = lambda : list(map(int, input().split()))\n\t(h, w) = inp()\n\ta = [inp() for _ in range(h)]\n\tb = [inp() for _ in range(h)]\n\td = [[0] * w for _ in range(h)]\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\td[i][j] = abs(a[i][j] - b[i][j])\n\tzero = 80 * (h + w) + 2\n\tdp = [[0] * w for _ in range(h)]\n\tdp[0][0] = 1 << zero + d[0][0] | 1 << zero - d[0][0]\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tif i == 0:\n\t\t\t\tif j == 0:\n\t\t\t\t\tcontinue\n\t\t\t\telse:\n\t\t\t\t\tdp[i][j] = dp[i][j - 1] << d[i][j] | dp[i][j - 1] >> d[i][j]\n\t\t\telif j == 0:\n\t\t\t\tdp[i][j] = dp[i - 1][j] << d[i][j] | dp[i - 1][j] >> d[i][j]\n\t\t\telse:\n\t\t\t\tdp[i][j] = dp[i - 1][j] << d[i][j] | dp[i - 1][j] >> d[i][j]\n\t\t\t\tdp[i][j] = dp[i][j] | (dp[i][j - 1] << d[i][j] | dp[i][j - 1] >> d[i][j])\n\tans = dp[-1][-1]\n\tfor i in range(zero):\n\t\tif ans >> zero + i & 1 or ans >> zero - i & 1:\n\t\t\tprint(i)\n\t\t\treturn\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\nx = (h + w) * 80\ndp = [[0] * w for _ in range(h)]\nd = abs(a[0][0] - b[0][0])\ndp[0][0] = 1 << x - d\nfor i in range(h):\n\tfor (j, (ae, be)) in enumerate(zip(a[i], b[i])):\n\t\tif i == j == 0:\n\t\t\tcontinue\n\t\td = abs(ae - be)\n\t\tbt = 0\n\t\tif i != 0:\n\t\t\tbt |= dp[i - 1][j] << d\n\t\t\tbt |= dp[i - 1][j] >> d\n\t\tif j != 0:\n\t\t\tbt |= dp[i][j - 1] << d\n\t\t\tbt |= dp[i][j - 1] >> d\n\t\tdp[i][j] = bt\ndp = dp[-1][-1]\nb = bin(dp)[2:]\ncan_make = [i - x for (i, be) in enumerate(b[::-1]) if be == '1']\nans = min((x if x >= 0 else -x for x in can_make))\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nDiff = [[0] * (W + 1) for _ in range(H + 1)]\nM = 0\nfor i in range(H):\n\tfor j in range(W):\n\t\tm = abs(A[i][j] - B[i][j])\n\t\tDiff[i][j] = m\n\t\tM += m\ndp = [[0] * (W + 1) for _ in range(H + 1)]\ndp[0][0] |= 1 << Diff[i][j]\nfor i in range(0, H):\n\tfor j in range(0, W):\n\t\there = dp[i][j]\n\t\ts = Diff[i][j]\n\t\tni = nj = here << s | here >> s\n\t\tex = 0\n\t\tfor k in range(1, s + 1):\n\t\t\tif here >> k & 1:\n\t\t\t\tex |= 1 << s - k\n\t\tdp[i + 1][j] |= ni | ex\n\t\tdp[i][j + 1] |= nj | ex\na = dp[H - 1][W - 1]\nans = 0\nfor k in range(M + 1):\n\tif a >> k & 1:\n\t\tans = k\n\t\tbreak\nprint(k)\n", "import numpy as np\n(H, W) = map(int, input().split())\nred_map = np.array([input().split() for i in range(H)], dtype='int')\nblue_map = np.array([input().split() for i in range(H)], dtype='int')\nsub_map = abs(red_map - blue_map)\ndp = [[2020] * W for i in range(H)]\nmax_deviation = 2 ** (80 * (H + W))\nfor i in range(H):\n\tfor j in range(W):\n\t\tif not i and (not j):\n\t\t\tdp[i][j] = max_deviation << sub_map[i][j] | max_deviation >> sub_map[i][j]\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << sub_map[i][j] | dp[i - 1][j] >> sub_map[i][j]\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << sub_map[i][j] | dp[i][j - 1] >> sub_map[i][j]\npre_ans = dp[H - 1][W - 1] >> 80 * (H + W)\npre_ans_bit = format(pre_ans & -pre_ans, 'b')\nans = len(pre_ans_bit) - 1\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nfor i in range(H):\n\tB = list(map(int, input().split()))\n\tfor j in range(W):\n\t\tA[i][j] = abs(A[i][j] - B[j])\nD = 80 * (H + W) + 1\nD2 = D * 2\ndp = [[0] * W for i in range(H)]\ndp[0][0] |= 1 << D + A[0][0]\ndp[0][0] |= 1 << D - A[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i:\n\t\t\tdp[i][j] |= dp[i - 1][j] << A[i][j]\n\t\t\tdp[i][j] |= dp[i - 1][j] >> A[i][j]\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << A[i][j]\n\t\t\tdp[i][j] |= dp[i][j - 1] >> A[i][j]\nres = dp[-1][-1]\nans = 10 ** 18\nfor i in range(D2):\n\tif res >> i & 1:\n\t\tans = min(ans, abs(D - i))\nprint(ans)\n", "(H, W) = map(int, input().split())\nc = [list(map(int, input().split())) for i in range(H)]\nb = [list(map(int, input().split())) for i in range(H)]\na = [[0 for i in range(W)] for j in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\ta[i][j] = abs(c[i][j] - b[i][j])\ndp = [[0 for i in range(W)] for j in range(H)]\nX = 3200\ndp[0][0] = 1 << X + a[0][0] | 1 << X - a[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif 0 <= i < H and 0 <= j + 1 < W:\n\t\t\tdp[i][j + 1] |= dp[i][j] << a[i][j + 1]\n\t\t\tdp[i][j + 1] |= dp[i][j] >> a[i][j + 1]\n\t\tif 0 <= i + 1 < H and 0 <= j < W:\n\t\t\tdp[i + 1][j] |= dp[i][j] << a[i + 1][j]\n\t\t\tdp[i + 1][j] |= dp[i][j] >> a[i + 1][j]\nA = str(bin(dp[H - 1][W - 1]))[::-1]\nL = len(A)\nans = 3200\nfor i in range(L):\n\tif A[i] == '1':\n\t\tans = min(ans, abs(i - X))\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\narr = [set() for _ in range(W)]\narr[0].add(A[0][0] - B[0][0])\nfor x in range(1, W):\n\ts = arr[x]\n\td = A[0][x] - B[0][x]\n\tfor n in arr[x - 1]:\n\t\ts.add(abs(n + d))\n\t\ts.add(abs(n - d))\nfor y in range(1, H):\n\tnextarr = [set() for _ in range(W)]\n\tAy = A[y]\n\tBy = B[y]\n\tdh = H - y - 1\n\tfor x in range(W):\n\t\tnextset = nextarr[x]\n\t\td = Ay[x] - By[x]\n\t\tdw = W - x - 1\n\t\tlim = (dh + dw + 1) * 160\n\t\tif x >= 1:\n\t\t\tarr[x] |= nextarr[x - 1]\n\t\tfor n in arr[x]:\n\t\t\tif abs(n + d) <= lim:\n\t\t\t\tnextset.add(abs(n + d))\n\t\t\tif abs(n - d) <= lim:\n\t\t\t\tnextset.add(abs(n - d))\n\tarr = nextarr\nprint(min([abs(d) for d in arr[-1]]))\n", "f = lambda : map(int, input().split())\n(H, W) = f()\nA = [[*f()] for _ in [0] * H]\nB = [[*f()] for _ in [0] * H]\nG = [[set() for i in [0] * W] for j in [0] * H]\nG[0][0].add(0)\nfor h in range(H):\n\tfor w in range(W):\n\t\td = A[h][w] - B[h][w]\n\t\tfor a in G[h][w]:\n\t\t\tif h != H - 1:\n\t\t\t\tG[h + 1][w].add(abs(a + d))\n\t\t\t\tG[h + 1][w].add(abs(a - d))\n\t\t\tif w != W - 1:\n\t\t\t\tG[h][w + 1].add(abs(a + d))\n\t\t\t\tG[h][w + 1].add(abs(a - d))\nres = set()\nd = A[H - 1][W - 1] - B[H - 1][W - 1]\nfor a in G[H - 1][W - 1]:\n\tres.add(abs(a + d))\n\tres.add(abs(a - d))\nprint(min(res))\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nd = [[0] * W for j in range(H)]\nm = 80 * (H + W)\nd[0][0] = 1 << m\nfor h in range(H):\n\tfor w in range(W):\n\t\tx = abs(A[h][w] - B[h][w])\n\t\tif h > 0:\n\t\t\td[h][w] |= d[h - 1][w]\n\t\tif w > 0:\n\t\t\td[h][w] |= d[h][w - 1]\n\t\td[h][w] = d[h][w] << x | d[h][w] >> x\n(x, y) = (1 << m, 1 << m)\nfor i in range(99):\n\tif d[H - 1][W - 1] & x or d[H - 1][W - 1] & y:\n\t\tprint(i)\n\t\texit()\n\tx <<= 1\n\ty >>= 1\n", "import sys\nsys.setrecursionlimit(10 ** 6)\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep='\\n')\n\ndef MI():\n\treturn map(int, sys.stdin.readline().split())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef bin_out(aa):\n\tbb = [format(a, 'b') for a in aa]\n\tprint(bb)\n\ndef main():\n\t(h, w) = MI()\n\taa = LLI(h)\n\tbb = LLI(h)\n\tmax_val = 6400\n\tzero = 1 << max_val\n\tdp = [0] * w\n\tdp[0] = zero\n\tfor (i, (ar, br)) in enumerate(zip(aa, bb)):\n\t\tfor (j, (a, b)) in enumerate(zip(ar, br)):\n\t\t\td = abs(a - b)\n\t\t\tif j > 0:\n\t\t\t\tdp[j] |= dp[j - 1]\n\t\t\tdp[j] = dp[j] << d | dp[j] >> d\n\tgoal = dp[-1]\n\tfor ans in range(max_val + 1):\n\t\tif goal & zero << ans or goal & zero >> ans:\n\t\t\tprint(ans)\n\t\t\tbreak\nmain()\n", "def solve(h, w, A, B):\n\tcenter = 80 * (h + w - 1)\n\tC = [[abs(A[r][c] - B[r][c]) for c in range(w)] for r in range(h)]\n\tdp = [[0] * w for r in range(h)]\n\tdp[0][0] = 1 << center + C[0][0] | 1 << center - C[0][0]\n\tfor r in range(h):\n\t\tfor c in range(w):\n\t\t\tif r > 0:\n\t\t\t\tdp[r][c] |= dp[r - 1][c] << C[r][c] | dp[r - 1][c] >> C[r][c]\n\t\t\tif c > 0:\n\t\t\t\tdp[r][c] |= dp[r][c - 1] << C[r][c] | dp[r][c - 1] >> C[r][c]\n\tmask = bin(dp[-1][-1] >> center)\n\treturn mask[::-1].find('1')\n(h, w) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(h)]\nB = [list(map(int, input().split())) for i in range(h)]\nprint(solve(h, w, A, B))\n", "(H, W) = map(int, input().split())\nA = [[int(i) for i in input().split()] for j in range(H)]\nB = [[int(i) for i in input().split()] for j in range(H)]\ndp = [[0 for j in range(W)] for i in range(H)]\nM = 161 * 161\ndp[0][0] |= 1 << A[0][0] - B[0][0] + M\ndp[0][0] |= 1 << -A[0][0] + B[0][0] + M\nfor i in range(H):\n\tfor j in range(W):\n\t\tdij = abs(A[i][j] - B[i][j])\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << dij\n\t\t\tdp[i][j] |= dp[i - 1][j] >> dij\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] >> dij\n\t\t\tdp[i][j] |= dp[i][j - 1] << dij\nans = []\nfor k in range(2 * M + 1):\n\tif 1 << k & dp[-1][-1] != 0:\n\t\tans.append(abs(k - M))\nprint(min(ans))\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\nM = (H + W) * 80\ndp = [[0 for j in range(W)] for i in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i == 0:\n\t\t\tif j == 0:\n\t\t\t\tdp[i][j] = 1 << M << C[i][j]\n\t\t\telse:\n\t\t\t\tdp[i][j] |= dp[i][j - 1] >> C[i][j]\n\t\t\t\tdp[i][j] |= dp[i][j - 1] << C[i][j]\n\t\telse:\n\t\t\tif j != 0:\n\t\t\t\tdp[i][j] |= dp[i][j - 1] >> C[i][j]\n\t\t\t\tdp[i][j] |= dp[i][j - 1] << C[i][j]\n\t\t\tdp[i][j] |= dp[i - 1][j] >> C[i][j]\n\t\t\tdp[i][j] |= dp[i - 1][j] << C[i][j]\ndp = bin(dp[i][j])[2:]\ndp = dp[::-1]\nans = M\nfor (i, x) in enumerate(dp):\n\tif x == '1':\n\t\tans = min(ans, abs(i - M))\nprint(ans)\n", "import sys, queue, math, copy, itertools, bisect, collections, heapq\n\ndef main():\n\tLI = lambda : [int(x) for x in sys.stdin.readline().split()]\n\t(H, W) = LI()\n\tA = [LI() for _ in range(H)]\n\tB = [LI() for _ in range(H)]\n\tC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\n\tD = [[set() for _ in range(W + 1)] for _ in range(H + 1)]\n\tD[0][1] = {0}\n\tfor i in range(1, H + 1):\n\t\tfor j in range(1, W + 1):\n\t\t\tfor k in D[i - 1][j] | D[i][j - 1]:\n\t\t\t\tD[i][j].add(abs(k + C[i - 1][j - 1]))\n\t\t\t\tD[i][j].add(abs(k - C[i - 1][j - 1]))\n\tprint(min(D[-1][-1]))\nmain()\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nC = [[abs(a - b) for (a, b) in zip(arow, brow)] for (arow, brow) in zip(A, B)]\nofs = 80 * (H + W)\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = 1 << ofs + C[0][0] | 1 << ofs - C[0][0]\nfor (i, crow) in enumerate(C):\n\tfor (j, c) in enumerate(crow):\n\t\tif i:\n\t\t\tdp[i][j] = dp[i - 1][j] << c | dp[i - 1][j] >> c\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << c | dp[i][j - 1] >> c\nans = ofs * 2\nfor i in range(ofs * 2):\n\tif dp[-1][-1] & 1 << i:\n\t\tans = min(ans, abs(i - ofs))\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\n\ndef reverse_binary(n, width):\n\treturn int('{:0{width}b}'.format(n, width=width)[::-1], 2)\ndp = [[0 for _ in range(W)] for _ in range(H)]\ndp[0][0] = 1 << abs(A[0][0] - B[0][0])\nfor h in range(H):\n\tfor w in range(W):\n\t\tdiff = abs(A[h][w] - B[h][w])\n\t\tif w:\n\t\t\tdp[h][w] |= reverse_binary(dp[h][w - 1] & (1 << diff) - 1, diff) << 1\n\t\t\tdp[h][w] |= dp[h][w - 1] >> diff\n\t\t\tdp[h][w] |= dp[h][w - 1] << diff\n\t\tif h:\n\t\t\tdp[h][w] |= reverse_binary(dp[h - 1][w] & (1 << diff) - 1, diff) << 1\n\t\t\tdp[h][w] |= dp[h - 1][w] >> diff\n\t\t\tdp[h][w] |= dp[h - 1][w] << diff\ntmp = dp[-1][-1]\nans = 0\nwhile tmp & 1 == 0:\n\ttmp >>= 1\n\tans += 1\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = []\nA.append([0 for i in range(W + 1)])\nfor i in range(H):\n\ta = [0] + list(map(int, input().split()))\n\tA.append(a)\nB = []\nB.append([0 for i in range(W + 1)])\nfor i in range(H):\n\tb = [0] + list(map(int, input().split()))\n\tB.append(b)\nC = [[0 for i in range(W + 1)] for j in range(H + 1)]\nfor i in range(H + 1):\n\tfor j in range(W + 1):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\nST = 1 << 80 * 160 + 1\ndp = [[0 for i in range(W + 1)] for j in range(H + 1)]\ndp[0][1] = ST\nfor i in range(1, H + 1):\n\tfor j in range(1, W + 1):\n\t\tdp[i][j] |= dp[i - 1][j] << C[i][j] | dp[i - 1][j] >> C[i][j]\n\t\tdp[i][j] |= dp[i][j - 1] << C[i][j] | dp[i][j - 1] >> C[i][j]\nANS = list(bin(dp[-1][-1] >> 80 * 160 + 1))[::-1]\nfor i in range(len(ANS)):\n\tif ANS[i] == '1':\n\t\tprint(i)\n\t\texit()\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\ndif = []\nfor (aj, bj) in zip(a, b):\n\tdif.append([abs(aij - bij) for (aij, bij) in zip(aj, bj)])\ndp = [0] * w\ndp[0] = 1 << 6400\nfor i in range(h):\n\tdp[0] = dp[0] << dif[i][0] | dp[0] >> dif[i][0]\n\tfor j in range(1, w):\n\t\tdp[j] = dp[j - 1] << dif[i][j] | dp[j - 1] >> dif[i][j] | dp[j] << dif[i][j] | dp[j] >> dif[i][j]\nresult = list(format(dp[-1] >> 6400, 'b'))[::-1]\nans = 0\nfor i in range(len(result)):\n\tif result[i] == '1':\n\t\tprint(ans)\n\t\tbreak\n\telse:\n\t\tans += 1\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\n\ndef main():\n\t(h, w) = map(int, input().split())\n\tA = [list(map(int, input().split())) for i in range(h)]\n\tB = [list(map(int, input().split())) for i in range(h)]\n\tabss = [[abs(A[i][j] - B[i][j]) for j in range(w)] for i in range(h)]\n\tdp = [[0] * w for i in range(h)]\n\tdp[0][0] = 1 << abss[0][0] + 13000\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tif i != h - 1:\n\t\t\t\tdp[i + 1][j] = dp[i + 1][j] | dp[i][j] << abss[i + 1][j] | dp[i][j] >> abss[i + 1][j]\n\t\t\tif j != w - 1:\n\t\t\t\tdp[i][j + 1] = dp[i][j + 1] | dp[i][j] << abss[i][j + 1] | dp[i][j] >> abss[i][j + 1]\n\ta = 0\n\tans = dp[-1][-1]\n\twhile True:\n\t\tif ans & 1 << 13000 - a:\n\t\t\tprint(a)\n\t\t\tbreak\n\t\telif ans & 1 << 13000 + a:\n\t\t\tprint(a)\n\t\t\tbreak\n\t\ta += 1\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(H, W) = map(int, input().split())\nmaxK = 80 * 80 + 1\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\ndp = [[[0 for _ in range(maxK + 1)] for _ in range(W + 1)] for _ in range(H + 1)]\ndp[1][1][C[0][0]] = 1\nfor i in range(1, H + 1):\n\tfor j in range(1, W + 1):\n\t\tfor k in range(maxK):\n\t\t\tif dp[i - 1][j][k] == 1 or dp[i][j - 1][k] == 1:\n\t\t\t\t(k_candidate1, k_candidate2) = (abs(k - C[i - 1][j - 1]), abs(k + C[i - 1][j - 1]))\n\t\t\t\tif k_candidate1 < maxK:\n\t\t\t\t\tdp[i][j][k_candidate1] = 1\n\t\t\t\tif k_candidate2 < maxK:\n\t\t\t\t\tdp[i][j][k_candidate2] = 1\nfor k in range(maxK):\n\tif dp[H][W][k] == 1:\n\t\tprint(k)\n\t\tbreak\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nAB = [list(map(lambda x, y: abs(x - y), a, b)) for (a, b) in zip(A, B)]\ndp = [[[0] * 12801 for _ in range(W + 1)] for _ in range(H + 1)]\ndp[0][0][0] = 1\nfor h in range(H):\n\tfor w in range(W):\n\t\tab = AB[h][w]\n\t\tfor i in range(10000):\n\t\t\tif dp[h][w][i] == 1:\n\t\t\t\tdp[h + 1][w][i + ab] = 1\n\t\t\t\tdp[h + 1][w][abs(i - ab)] = 1\n\t\t\t\tdp[h][w + 1][i + ab] = 1\n\t\t\t\tdp[h][w + 1][abs(i - ab)] = 1\nfor i in range(1000):\n\tif dp[H][W - 1][i] == 1:\n\t\tprint(i)\n\t\tbreak\n", "import sys\nfrom collections import deque\n(h, w) = map(int, input().split())\ngraph = []\nfor i in range(h):\n\ta = list(map(int, sys.stdin.readline().split()))\n\tgraph.append(a)\nfor i in range(h):\n\tb = list(map(int, sys.stdin.readline().split()))\n\tfor j in range(w):\n\t\tgraph[i][j] = abs(graph[i][j] - b[j])\nresult = [[0] * w for _ in range(h)]\nresult[0][0] = 1 << graph[0][0]\n\ndef ts(a, b):\n\tresult = 0\n\tfor i in range(b + 1):\n\t\tif a >> i & 1 > 0:\n\t\t\tresult |= 1 << b >> i\n\treturn result\nfor i in range(1, h + w - 1):\n\tfor j in range(max(0, i - (w - 1)), min(i + 1, h)):\n\t\tps = 0\n\t\tnt = graph[j][i - j]\n\t\tif j > 0:\n\t\t\tk = result[j - 1][i - j]\n\t\t\tresult[j][i - j] |= k << nt | k >> nt | ts(k, nt)\n\t\tif i - j > 0:\n\t\t\tk = result[j][i - j - 1]\n\t\t\tresult[j][i - j] |= k << nt | k >> nt | ts(k, nt)\nans = result[h - 1][w - 1]\nans = (-ans & ans).bit_length() - 1\nprint(ans)\n", "import sys\nsys.setrecursionlimit(2147483647)\nINF = float('inf')\nMOD = 10 ** 9 + 7\ninput = lambda : sys.stdin.readline().rstrip()\n\ndef resolve():\n\tofs = 6400\n\t(h, w) = map(int, input().split())\n\tA = [list(map(int, input().split())) for _ in range(h)]\n\tB = [list(map(int, input().split())) for _ in range(h)]\n\tdp = [[0] * w for _ in range(h)]\n\tx = abs(A[0][0] - B[0][0])\n\tdp[0][0] |= 1 << ofs + x | 1 << ofs - x\n\tfrom itertools import product\n\tfor (i, j) in product(range(h), range(w)):\n\t\tx = abs(A[i][j] - B[i][j])\n\t\tt = 0\n\t\tif i - 1 >= 0:\n\t\t\tt |= dp[i - 1][j]\n\t\tif j - 1 >= 0:\n\t\t\tt |= dp[i][j - 1]\n\t\tdp[i][j] |= t << x | t >> x\n\tfor (i, s) in enumerate(bin(dp[-1][-1])[-ofs - 1:]):\n\t\tif s == '1':\n\t\t\tprint(i)\n\t\t\treturn\nresolve()\n", "(H, W) = map(int, input().split())\nAB = []\nmax_ab = 0\nfor i in range(H):\n\tAB.append(list(map(int, input().split())))\n\tmax_ab = max(max_ab, max(AB[-1]))\nfor i in range(H):\n\tAB[i] = [abs(AB[i][j] - int(b)) for (j, b) in enumerate(input().split())]\nbase = max_ab * (H + W)\ndp = [[1 << base for w in range(W)] for h in range(H)]\ndp[0][0] = 1 << base + AB[0][0] | 1 << base - AB[0][0]\nfor h in range(1, H):\n\tdp[h][0] = dp[h - 1][0] << AB[h][0] | dp[h - 1][0] >> AB[h][0]\nfor w in range(1, W):\n\tdp[0][w] = dp[0][w - 1] << AB[0][w] | dp[0][w - 1] >> AB[0][w]\nfor h in range(1, H):\n\tfor w in range(1, W):\n\t\tdp[h][w] = dp[h - 1][w] << AB[h][w] | dp[h - 1][w] >> AB[h][w] | dp[h][w - 1] << AB[h][w] | dp[h][w - 1] >> AB[h][w]\npositive = bin(dp[H - 1][W - 1] >> base)\nprint(positive[::-1].find('1'))\n", "import sys\nimport numpy as np\nsr = lambda : sys.stdin.readline().rstrip()\nir = lambda : int(sr())\nlr = lambda : list(map(int, sr().split()))\n(H, W) = lr()\nA = np.array([lr() for _ in range(H)])\nB = np.array([lr() for _ in range(H)])\ndiff = np.abs(A - B).tolist()\nX = (H + W) * 80\nL = X + X + 1\ndp = [[np.zeros(L, np.bool) for _ in range(W)] for _ in range(H)]\ndi = diff[0][0]\ndp[0][0][X + di] = 1\ndp[0][0][X - di] = 1\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i == 0 and j == 0:\n\t\t\tcontinue\n\t\tdi = diff[i][j]\n\t\tif i > 0:\n\t\t\tprev = dp[i - 1][j]\n\t\t\tdp[i][j][di:] |= prev[:L - di]\n\t\t\tdp[i][j][:L - di] |= prev[di:]\n\t\tif j > 0:\n\t\t\tprev = dp[i][j - 1]\n\t\t\tdp[i][j][di:] |= prev[:L - di]\n\t\t\tdp[i][j][:L - di] |= prev[di:]\ndp = dp[-1][-1][X:]\npossible = np.nonzero(dp)[0]\nanswer = possible.min()\nprint(answer)\n", "(H, W) = map(int, input().split())\nA = [[0] * W for i in range(H)]\nB = [[0] * W for i in range(H)]\nfor i in range(H):\n\tinf = [int(c) for c in input().split()]\n\tfor j in range(W):\n\t\tA[i][j] = inf[j]\nfor i in range(H):\n\tinf = [int(c) for c in input().split()]\n\tfor j in range(W):\n\t\tB[i][j] = inf[j]\nX = (H + W) * 80\ndp = [[0] * W for i in range(H)]\nd = abs(A[0][0] - B[0][0])\ndp[0][0] = 1 << X + d\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i == 0 and j == 0:\n\t\t\tcontinue\n\t\td = abs(A[i][j] - B[i][j])\n\t\tif i != 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] >> d\n\t\t\tdp[i][j] |= dp[i - 1][j] << d\n\t\tif j != 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] >> d\n\t\t\tdp[i][j] |= dp[i][j - 1] << d\ns = bin(dp[-1][-1])[2:]\nl = len(s) - 1\nans = float('inf')\nfor i in range(l, -1, -1):\n\tif s[i] == '1':\n\t\tm = abs(l - i - X)\n\t\tif m < ans:\n\t\t\tans = m\nprint(ans)\n", "(h, w) = map(int, input().split())\nlsa = [list(map(int, input().split())) for i in range(h)]\nlsb = [list(map(int, input().split())) for i in range(h)]\nls = [[abs(lsa[i][j] - lsb[i][j]) for j in range(w)] for i in range(h)]\nbias = 80 * 80 * 80\ndp = [[0 for _ in range(w)] for _ in range(h)]\ndp[0][0] = 1 << ls[0][0] + bias\nfor i in range(h):\n\tfor j in range(w):\n\t\tif j != 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << ls[i][j]\n\t\t\tdp[i][j] |= dp[i][j - 1] >> ls[i][j]\n\t\tif i != 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << ls[i][j]\n\t\t\tdp[i][j] |= dp[i - 1][j] >> ls[i][j]\nans = dp[h - 1][w - 1]\nidx = 0\nwhile 1:\n\tif 1 << bias + idx & ans or 1 << bias - idx & ans:\n\t\tbreak\n\tidx += 1\nprint(idx)\n", "import numpy as np\n(H, W) = list(map(int, input().split()))\nA = np.array([list(map(int, input().split())) for _ in range(H)])\nB = np.array([list(map(int, input().split())) for _ in range(H)])\nC = abs(A - B)\nD = 80 * (H + W + 1) + 10\nD2 = D * 2\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = 1 << D - int(C[0][0])\ndp[0][0] |= 1 << D + int(C[0][0])\ndp = np.array(dp)\nfor h in range(H):\n\tfor w in range(W):\n\t\ttmp = int(C[h][w])\n\t\tif h:\n\t\t\tdp[h][w] |= dp[h - 1][w] << tmp\n\t\t\tdp[h][w] |= dp[h - 1][w] >> tmp\n\t\tif w:\n\t\t\tdp[h][w] |= dp[h][w - 1] << tmp\n\t\t\tdp[h][w] |= dp[h][w - 1] >> tmp\nans = D2\ntmp = dp[H - 1][W - 1]\nfor i in range(D2):\n\tif tmp >> i & 1:\n\t\tans = min(ans, abs(i - D))\nprint(ans)\n", "from itertools import product\n\ndef offset(a, b):\n\tresult = 0\n\tif b == 0:\n\t\treturn 0\n\tfor i in range(b + 1):\n\t\tif a >> i & 1:\n\t\t\tresult |= 1 << b >> i\n\treturn result\n(H, W) = map(int, input().split())\ndiff = [list(map(int, input().split())) for _ in range(H)]\nM = 80\nfor i in range(H):\n\tB = list(map(int, input().split()))\n\tfor j in range(W):\n\t\tdiff[i][j] = abs(diff[i][j] - B[j])\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = 1 << diff[0][0]\nfor (i, j) in product(range(H), range(W)):\n\tif (i, j) == (H - 1, W - 1):\n\t\tbreak\n\tif i + 1 < H:\n\t\tk = diff[i + 1][j]\n\t\tdp[i + 1][j] |= dp[i][j] >> k | dp[i][j] << k | offset(dp[i][j], k)\n\tif j + 1 < W:\n\t\tk = diff[i][j + 1]\n\t\tdp[i][j + 1] |= dp[i][j] >> k | dp[i][j] << k | offset(dp[i][j], k)\nans = dp[H - 1][W - 1]\nprint((ans & -ans).bit_length() - 1)\n", "def main():\n\t(h, w) = list(map(int, input().split()))\n\tL = 80 * (h + w) + 1\n\ta = [list(map(int, input().split())) for i in range(h)]\n\tb = [list(map(int, input().split())) for i in range(h)]\n\tx = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]\n\tL = 12800\n\tstate = [[0] * w for _ in range(h)]\n\tdelta = x[0][0]\n\tstate[0][0] = 2 ** L >> delta | 2 ** L << delta\n\tfor j in range(1, w):\n\t\tdelta = x[0][j]\n\t\tstate[0][j] = state[0][j - 1] >> delta | state[0][j - 1] << delta\n\tfor i in range(1, h):\n\t\tdelta = x[i][0]\n\t\tstate[i][0] = state[i - 1][0] >> delta | state[i - 1][0] << delta\n\tfor i in range(1, h):\n\t\tfor j in range(1, w):\n\t\t\tdelta = x[i][j]\n\t\t\tstate[i][j] = state[i][j - 1] >> delta | state[i][j - 1] << delta\n\t\t\tstate[i][j] |= state[i - 1][j] >> delta | state[i - 1][j] << delta\n\tans = 10 ** 9\n\tfor i in range(L * 2):\n\t\tif state[h - 1][w - 1] & 1:\n\t\t\tans = min(ans, abs(i - L))\n\t\tstate[h - 1][w - 1] >>= 1\n\tprint(ans)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "def max2(x, y):\n\treturn x if x > y else y\n(H, W) = map(int, input().split())\nA = []\nB = []\nofs = 80 * H * W\nfor _ in range(H):\n\tA.append(list(map(int, input().split())))\nfor _ in range(H):\n\tB.append(list(map(int, input().split())))\nd = [[0] * W for _ in range(H)]\nfor h in range(H):\n\tfor w in range(W):\n\t\td[h][w] = abs(A[h][w] - B[h][w])\ndp = [[0 for _ in range(W)] for _ in range(H)]\ndp[0][0] = 1 << ofs\ndp[0][0] = dp[0][0] << d[0][0] | dp[0][0] >> d[0][0]\nfor h in range(H):\n\tfor w in range(W):\n\t\tif h < H - 1:\n\t\t\tdp[h + 1][w] |= dp[h][w] << d[h + 1][w] | dp[h][w] >> d[h + 1][w]\n\t\tif w < W - 1:\n\t\t\tdp[h][w + 1] |= dp[h][w] << d[h][w + 1] | dp[h][w] >> d[h][w + 1]\nres = dp[-1][-1] >> ofs\nprint((-res & res).bit_length() - 1)\n", "(H, W) = map(int, input().split())\nA = [[int(a) for a in input().split()] for _ in range(H)]\nB = [[int(a) for a in input().split()] for _ in range(H)]\nC = [[A[i][j] - B[i][j] for j in range(W)] for i in range(H)]\nX = [[0] * W for _ in range(H)]\nX[0][0] = 1 << 80 + C[0][0] | 1 << 80 - C[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i:\n\t\t\tX[i][j] |= X[i - 1][j] << 80 + C[i][j] | X[i - 1][j] << 80 - C[i][j]\n\t\tif j:\n\t\t\tX[i][j] |= X[i][j - 1] << 80 + C[i][j] | X[i][j - 1] << 80 - C[i][j]\ns = bin(X[-1][-1] + (1 << 13000))\nmi = 1 << 100\nfor i in range(len(s)):\n\tif s[-i - 1] == '1':\n\t\tmi = min(mi, abs(i - (H + W - 1) * 80))\nprint(mi)\n", "import sys\nimport numpy as np\ninput = sys.stdin.readline\n(H, W) = list(map(int, input().split()))\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nC = [[abs(a - b) for (a, b) in zip(la, lb)] for (la, lb) in zip(A, B)]\nMAX = 160 * (80 + 80) + 10\nvals = np.zeros((W, MAX)).astype(bool)\ntemp = np.zeros(MAX).astype(bool)\ntemp[C[0][0]] = True\nfor y in range(H):\n\tfor x in range(W):\n\t\tc = C[y][x]\n\t\tif c == 0:\n\t\t\tif y > 0:\n\t\t\t\ttemp |= vals[x]\n\t\t\tif x > 0:\n\t\t\t\ttemp |= vals[x - 1]\n\t\t\tvals[x] &= False\n\t\t\tvals[x] |= temp\n\t\t\ttemp &= False\n\t\telse:\n\t\t\tif y > 0:\n\t\t\t\ttemp[c:] |= vals[x][:-c]\n\t\t\t\ttemp[:c + 1] |= vals[x][:c + 1][::-1]\n\t\t\t\ttemp[:-c] |= vals[x][c:]\n\t\t\tif x > 0:\n\t\t\t\ttemp[c:] |= vals[x - 1][:-c]\n\t\t\t\ttemp[:c + 1] |= vals[x - 1][:c + 1][::-1]\n\t\t\t\ttemp[:-c] |= vals[x - 1][c:]\n\t\t\tvals[x] &= False\n\t\t\tvals[x] |= temp\n\t\t\ttemp &= False\nprint(np.where(vals[W - 1])[0][0])\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\ndp = [0] * W\ndp[0] = s = 1 << 6400\nfor (a, b) in zip(A, B):\n\tfor (j, (aa, bb)) in enumerate(zip(a, b)):\n\t\td = abs(aa - bb)\n\t\tif j > 0:\n\t\t\tdp[j] |= dp[j - 1]\n\t\tdp[j] = dp[j] << d | dp[j] >> d\ng = dp[-1]\nfor i in range(6401):\n\tif g & s << i or g & s >> i:\n\t\tprint(i)\n\t\tquit()\n", "import sys\nsys.setrecursionlimit(10 ** 7)\ninput = sys.stdin.readline\nf_inf = float('inf')\nmod = 10 ** 9 + 7\n\ndef resolve():\n\t(H, W) = map(int, input().split())\n\tA = [list(map(int, input().split())) for _ in range(H)]\n\tB = [list(map(int, input().split())) for _ in range(H)]\n\tdp = [[set() for _ in range(W)] for _ in range(H)]\n\tdp[0][0] = {abs(A[0][0] - B[0][0])}\n\tfor h in range(H):\n\t\tfor w in range(W):\n\t\t\t(a, b) = (A[h][w], B[h][w])\n\t\t\tif w - 1 >= 0:\n\t\t\t\tfor num in dp[h][w - 1]:\n\t\t\t\t\tdp[h][w].add(abs(num + a - b))\n\t\t\t\t\tdp[h][w].add(abs(-num + a - b))\n\t\t\tif h - 1 >= 0:\n\t\t\t\tfor num in dp[h - 1][w]:\n\t\t\t\t\tdp[h][w].add(abs(num + a - b))\n\t\t\t\t\tdp[h][w].add(abs(-num + a - b))\n\tres = f_inf\n\tfor num in dp[-1][-1]:\n\t\tres = min(res, abs(num))\n\tprint(res)\nresolve()\n", "e = enumerate\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\ndp = [0] * w\nc = 13000\nfor (i, (a, b)) in e(zip(a, b)):\n\tfor (j, (x, y)) in e(zip(a, b)):\n\t\tx = abs(x - y)\n\t\tif i == j == 0:\n\t\t\tdp[j] = 2 ** c << x\n\t\t\tcontinue\n\t\tt = 0\n\t\tif j:\n\t\t\tt |= dp[j - 1] << x\n\t\t\tt |= dp[j - 1] >> x\n\t\tif i:\n\t\t\tt |= dp[j] << x\n\t\t\tt |= dp[j] >> x\n\t\tdp[j] = t\n(*a,) = map(int, bin(dp[w - 1])[2:].zfill(26001))\nprint(min([i for (i, f) in e(a[13000:]) if f] + [i for (i, f) in e(a[13000::-1]) if f]))\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nassert all((len(row) == W for row in A))\nassert all((len(row) == W for row in B))\ntable = [[set() for j in range(W)] for i in range(H)]\ntable[0][0].add(abs(A[0][0] - B[0][0]))\nfor i in range(H):\n\tif i >= 2:\n\t\ttable[i - 2] = None\n\tfor j in range(W):\n\t\tprev = table[i - 1][j] if i > 0 else set()\n\t\tprev |= table[i][j - 1] if j > 0 else set()\n\t\tfor pdiff in prev:\n\t\t\tdiff = A[i][j] - B[i][j]\n\t\t\ttable[i][j].add(abs(pdiff + diff))\n\t\t\ttable[i][j].add(abs(pdiff - diff))\nm = min((diff for diff in table[H - 1][W - 1]))\nprint(m)\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\ngrid = [[0 for i in range(w)] for j in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tgrid[i][j] = abs(a[i][j] - b[i][j])\ndp = [[0 for j in range(w)] for k in range(h)]\nbuf = (h + w) * 80\nfor i in range(h):\n\tfor j in range(w):\n\t\tt = grid[i][j]\n\t\tif i == j == 0:\n\t\t\tdp[i][j] = 1 << buf + t | 1 << buf - t\n\t\tif j > 0:\n\t\t\tdp[i][j] = dp[i][j] | dp[i][j - 1] << t | dp[i][j - 1] >> t\n\t\tif i > 0:\n\t\t\tdp[i][j] = dp[i][j] | dp[i - 1][j] << t | dp[i - 1][j] >> t\nfor i in range(buf):\n\tif dp[h - 1][w - 1] & 1 << buf + i or dp[h - 1][w - 1] & 1 << buf - i:\n\t\tprint(i)\n\t\treturn\n", "import numpy as np\n(H, W) = list(map(int, input().split()))\nA = [[0] * W for i in range(H)]\nB = [[0] * W for i in range(H)]\nfor i in range(H):\n\tinf = [int(c) for c in input().split()]\n\tfor j in range(W):\n\t\tA[i][j] = inf[j]\nfor i in range(H):\n\tinf = [int(c) for c in input().split()]\n\tfor j in range(W):\n\t\tB[i][j] = inf[j]\nX = (H + W) * 80\nL = X + X + 1\ndp = [[0] * W for _ in range(H)]\nd = abs(A[0][0] - B[0][0])\ndp[0][0] = np.zeros(L, np.bool)\ndp[0][0][X + d] = 1\nfor h in range(H):\n\tfor (w, (a, b)) in enumerate(zip(A[h], B[h])):\n\t\tif h == w == 0:\n\t\t\tcontinue\n\t\td = abs(a - b)\n\t\tx = np.zeros(L, np.bool)\n\t\tif h != 0:\n\t\t\tx[d:] |= dp[h - 1][w][:L - d]\n\t\t\tx[:L - d] |= dp[h - 1][w][d:]\n\t\tif w != 0:\n\t\t\tx[d:] |= dp[h][w - 1][:L - d]\n\t\t\tx[:L - d] |= dp[h][w - 1][d:]\n\t\tdp[h][w] = x\ndp2 = dp[-1][-1]\ncan_make = np.where(dp2)[0] - X\nanswer = np.abs(can_make).min()\nprint(answer)\n", "import sys\ninput = sys.stdin.buffer.readline\n\ndef main():\n\t(h, w) = map(int, input().split())\n\tA = [list(map(int, input().split())) for _ in range(h)]\n\tB = [list(map(int, input().split())) for _ in range(h)]\n\tC = [[0] * w for _ in range(h)]\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tC[i][j] = abs(A[i][j] - B[i][j])\n\tD = [[0] * w for _ in range(h)]\n\tD[0][0] = 1 << C[0][0] + 5000 | 1 >> C[0][0] + 5000\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tif i > 0:\n\t\t\t\tD[i][j] = D[i][j] | D[i - 1][j] << C[i][j] | D[i - 1][j] >> C[i][j]\n\t\t\tif j > 0:\n\t\t\t\tD[i][j] = D[i][j] | D[i][j - 1] << C[i][j] | D[i][j - 1] >> C[i][j]\n\tval = D[-1][-1]\n\tans = 5000\n\tfor i in range(10000):\n\t\tif val >> i & 1:\n\t\t\tans = min(ans, abs(i - 5000))\n\tprint(ans)\nmain()\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\nM = (H + W) * 80\ndp = [[0] * W for _ in range(H)]\ndp[0][0] |= 1 << M - C[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i == j == 0:\n\t\t\tcontinue\n\t\tbit = 0\n\t\tif i > 0:\n\t\t\tbit |= dp[i - 1][j]\n\t\tif j > 0:\n\t\t\tbit |= dp[i][j - 1]\n\t\tdp[i][j] = bit >> C[i][j] | bit << C[i][j]\nans = M\nfor i in range(M + 1):\n\tif dp[-1][-1] >> i & 1:\n\t\tans = min(ans, abs(M - i))\nprint(ans)\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\ta[i][j] = abs(a[i][j] - b[i][j])\nbase = 2 ** 12800 - 1\ndp = [[0] * (w + 1) for _ in range(h + 1)]\ndp[1][1] = 2 ** 6400 >> a[0][0] | 2 ** 6400 << a[0][0] & base\nfor i in range(1, h + 1):\n\tfor j in range(1, w + 1):\n\t\tif (i == 1) & (j == 1):\n\t\t\tdp[1][1] = 2 ** 6400 >> a[0][0] | 2 ** 6400 << a[0][0] & base\n\t\t\tcontinue\n\t\tdp[i][j] = (dp[i - 1][j] >> a[i - 1][j - 1] | dp[i - 1][j] << a[i - 1][j - 1] | dp[i][j - 1] >> a[i - 1][j - 1] | dp[i][j - 1] << a[i - 1][j - 1]) & base\nans = 6400\nans_bit = dp[-1][-1]\nfor i in range(6300, 6500):\n\tif ans_bit >> i & 1 == 1:\n\t\tans = min(ans, abs(6400 - i))\nprint(ans)\n", "import sys\ninput = sys.stdin.readline\nsys.setrecursionlimit(10 ** 5)\n(H, W) = map(int, input().split())\nA = [[int(i) for i in input().split()] for _ in range(H)]\nB = [[int(i) for i in input().split()] for _ in range(H)]\nC = [[abs(A[y][x] - B[y][x]) for x in range(W)] for y in range(H)]\nN = 13000\nhalf = N // 2\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = 1 << half - C[0][0] | 1 << half + C[0][0]\nfor y in range(H):\n\tfor x in range(W):\n\t\tif y != 0:\n\t\t\tdp[y][x] |= dp[y - 1][x] >> C[y][x] | dp[y - 1][x] << C[y][x]\n\t\tif x != 0:\n\t\t\tdp[y][x] |= dp[y][x - 1] >> C[y][x] | dp[y][x - 1] << C[y][x]\nb = bin(dp[-1][-1])[2:][::-1]\nret = float('inf')\nfor (k, v) in enumerate(b):\n\tif v == '1':\n\t\tret = min(ret, abs(k - half))\nprint(ret)\n", "def main():\n\t(H, W) = map(int, input().split())\n\tN = 80 * (H + W) // 2\n\tA = [list(map(int, input().split())) for _ in range(H)]\n\tB = [list(map(int, input().split())) for _ in range(H)]\n\tdp = [[set() for _ in range(W + 1)] for _ in range(2)]\n\tdp[0][1].add(0)\n\n\tdef ltN(x):\n\t\treturn x <= N\n\tfor i in range(H):\n\t\tdp[i + 1 & 1] = [set() for _ in range(W + 1)]\n\t\tfor j in range(W):\n\t\t\tdiff = abs(A[i][j] - B[i][j])\n\t\t\ttmp = set()\n\t\t\tfor x in dp[i & 1][j + 1]:\n\t\t\t\ttmp.add(abs(x + diff))\n\t\t\t\ttmp.add(abs(x - diff))\n\t\t\tfor x in dp[i + 1 & 1][j]:\n\t\t\t\ttmp.add(abs(x + diff))\n\t\t\t\ttmp.add(abs(x - diff))\n\t\t\tdp[i + 1 & 1][j + 1] = tmp\n\tprint(min(dp[H & 1][W]))\nmain()\n", "(H, W) = map(int, input().split())\nA = [tuple(map(int, input().split())) for _ in range(H)]\nB = [tuple(map(int, input().split())) for _ in range(H)]\nC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\nD = 80 * (H + W) + 1\nD2 = D * 2\ndp = [[0] * W for _ in range(H)]\ndp[0][0] |= 1 << D + C[0][0]\ndp[0][0] |= 1 << D - C[0][0]\nfor h in range(H):\n\tfor w in range(W):\n\t\tc = C[h][w]\n\t\tif h >= 1:\n\t\t\tdp[h][w] |= dp[h - 1][w] << c\n\t\t\tdp[h][w] |= dp[h - 1][w] >> c\n\t\tif w >= 1:\n\t\t\tdp[h][w] |= dp[h][w - 1] << c\n\t\t\tdp[h][w] |= dp[h][w - 1] >> c\nans = D2\ntmp = dp[H - 1][W - 1]\nfor i in range(D2):\n\tif tmp >> i & 1:\n\t\tans = min(ans, abs(i - D))\nprint(ans)\n", "import sys, math, itertools, heapq, collections, bisect, copy\ninput = lambda : sys.stdin.buffer.readline().rstrip().decode('utf-8')\nsys.setrecursionlimit(10 ** 7)\ninf = float('inf')\nmod = 10 ** 9 + 7\nans = inf\ncount = 0\npro = 1\n(h, w) = map(int, input().split())\nA = [tuple(map(int, input().split())) for i in range(h)]\nB = [tuple(map(int, input().split())) for i in range(h)]\nK = 160 * 80\ndp = [[0] * w for i in range(h)]\ndp[0][0] = 1 << K\nfor i in range(h):\n\tfor j in range(w):\n\t\td = abs(A[i][j] - B[i][j])\n\t\tif i - 1 >= 0:\n\t\t\tdp[i][j] |= dp[i - 1][j]\n\t\tif j - 1 >= 0:\n\t\t\tdp[i][j] |= dp[i][j - 1]\n\t\tdp[i][j] = dp[i][j] << d | dp[i][j] >> d\nans = K\nfor i in range(2 * K):\n\tif dp[h - 1][w - 1] & 1 << i > 0:\n\t\tans = min(ans, abs(K - i))\nprint(ans)\n", "(R, C) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(R)]\nB = [list(map(int, input().split())) for _ in range(R)]\ndp = [0] * C\ndp[0] = s = 1 << 6400\nfor (row_a, row_b) in zip(A, B):\n\tfor (i, (a, b)) in enumerate(zip(row_a, row_b)):\n\t\td = abs(a - b)\n\t\tif i > 0:\n\t\t\tdp[i] |= dp[i - 1]\n\t\tdp[i] = dp[i] << d | dp[i] >> d\ng = dp[-1]\nfor i in range(6401):\n\tif g & s << i or g & s >> i:\n\t\tprint(i)\n\t\tquit()\n", "(h, w) = list(map(int, input().split()))\na = []\nfor i in range(h):\n\tai = list(map(int, input().split()))\n\ta.append(ai)\nfor i in range(h):\n\tbi = list(map(int, input().split()))\n\tfor j in range(w):\n\t\ta[i][j] -= bi[j]\n\t\ta[i][j] = abs(a[i][j])\ndp = [[0 for j in range(w)] for i in range(h)]\na2 = [a[i][j] for i in range(h) for j in range(w)]\nmxa = max(a2)\ntmp = 1 << mxa * (h + w) + 10\ndp[0][0] |= tmp << a[0][0]\ndp[0][0] |= tmp >> a[0][0]\nfor j in range(1, w):\n\tdp[0][j] = dp[0][j - 1] << a[0][j]\n\tdp[0][j] |= dp[0][j - 1] >> a[0][j]\nfor i in range(1, h):\n\tfor j in range(w):\n\t\tdp[i][j] = dp[i - 1][j] << a[i][j]\n\t\tdp[i][j] |= dp[i - 1][j] >> a[i][j]\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << a[i][j]\n\t\t\tdp[i][j] |= dp[i][j - 1] >> a[i][j]\ntmp1 = dp[h - 1][w - 1]\ntmp1 >>= mxa * (h + w) + 10\nfor k in range(mxa * (h + w) + 10):\n\tif tmp1 & 1:\n\t\tprint(k)\n\t\treturn\n\ttmp1 >>= 1\n", "import time\nstart = time.time()\n(H, W) = [int(s) for s in input().split()]\ninls = [[int(s) for s in input().split()] for _ in range(H)]\nfor i in range(H):\n\tx = [int(s) for s in input().split()]\n\tfor j in range(W):\n\t\tinls[i][j] = abs(inls[i][j] - x[j])\ndp = [[set() for _ in range(W)] for _ in range(H)]\ndp[0][0].add(inls[0][0])\nfor i in range(H):\n\tfor j in range(W):\n\t\tx = 80 * (H + W - i - j)\n\t\tfor e in dp[i - 1][j]:\n\t\t\tif e + inls[i][j] < x:\n\t\t\t\tdp[i][j].add(e + inls[i][j])\n\t\t\tdp[i][j].add(abs(e - inls[i][j]))\n\t\tfor e in dp[i][j - 1]:\n\t\t\tif e + inls[i][j] < x:\n\t\t\t\tdp[i][j].add(e + inls[i][j])\n\t\t\tdp[i][j].add(abs(e - inls[i][j]))\n\tif time.time() - start > 1.7:\n\t\tdp[H - 1][W - 1].add(0)\n\t\tbreak\nprint(min(dp[H - 1][W - 1]))\n", "import sys\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\nwrite = sys.stdout.write\n\ndef solve():\n\tofs = 700\n\t(h, w) = map(int, readline().split())\n\tA = [list(map(int, readline().split())) for i in range(h)]\n\tB = [list(map(int, readline().split())) for i in range(h)]\n\tdp = [0] * (w + 1)\n\tx = abs(A[0][0] - B[0][0])\n\tdp[0] = 1 << ofs\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tx = abs(A[i][j] - B[i][j])\n\t\t\tt = dp[j] | dp[j - 1]\n\t\t\tdp[j] = t << x | t >> x\n\tfor (i, s) in enumerate(bin(dp[w - 1])[-ofs - 1:]):\n\t\tif int(s):\n\t\t\twrite('%d\\n' % i)\n\t\t\treturn\nsolve()\n", "(H, W) = map(int, input().split())\nA = []\nB = []\nabs_diff = [[0] * (W + 1) for h in range(H + 1)]\nfor h in range(H):\n\tA.append(list(map(int, input().split())))\nfor h in range(H):\n\tB.append(list(map(int, input().split())))\nmax_diff = 0\nfor h in range(H):\n\tfor w in range(W):\n\t\td = abs(A[h][w] - B[h][w])\n\t\tmax_diff = max(max_diff, d)\n\t\tabs_diff[h + 1][w + 1] = d\nbase = max_diff * (H + W)\ndp = [[0 for w in range(W + 1)] for h in range(H + 1)]\ndp[0][1] = dp[1][0] = 1 << base\nfor h in range(1, H + 1):\n\tfor w in range(1, W + 1):\n\t\tdp[h][w] = dp[h - 1][w] << abs_diff[h][w] | dp[h - 1][w] >> abs_diff[h][w] | dp[h][w - 1] << abs_diff[h][w] | dp[h][w - 1] >> abs_diff[h][w]\npositive = bin(dp[H][W] >> base)\nprint(positive[::-1].find('1'))\n", "def main():\n\t(H, W) = map(int, input().split())\n\tMAX_BIAS = 80 * (H + W - 1)\n\tA = []\n\tfor _ in range(H):\n\t\tA += map(int, input().split())\n\tB = []\n\tfor _ in range(H):\n\t\tB += map(int, input().split())\n\tdp = [0] * (H * W)\n\tdp[0] |= 1 << MAX_BIAS\n\tfor r in range(H):\n\t\tfor c in range(W):\n\t\t\tp = r * W + c\n\t\t\td = abs(A[p] - B[p])\n\t\t\tx = dp[p]\n\t\t\tif r > 0:\n\t\t\t\tx |= dp[p - W]\n\t\t\tif c > 0:\n\t\t\t\tx |= dp[p - 1]\n\t\t\tdp[p] = x << d | x >> d\n\tans = MAX_BIAS\n\tfor j in range(2 * MAX_BIAS + 1):\n\t\tif dp[H * W - 1] >> j & 1:\n\t\t\tt = j - MAX_BIAS\n\t\t\tif ans > abs(t):\n\t\t\t\tans = abs(t)\n\tprint(ans)\nmain()\n", "import sys\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\nwrite = sys.stdout.write\n\ndef resolve():\n\tofs = 3200\n\t(h, w) = map(int, readline().split())\n\tA = [list(map(int, readline().split())) for i in range(h)]\n\tB = [list(map(int, readline().split())) for i in range(h)]\n\tdp = [[0] * w for _ in range(h)]\n\tx = abs(A[0][0] - B[0][0])\n\tdp[0][0] |= 1 << ofs + x | 1 << ofs - x\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tx = abs(A[i][j] - B[i][j])\n\t\t\tt = 0\n\t\t\tif i - 1 >= 0:\n\t\t\t\tt |= dp[i - 1][j]\n\t\t\tif j - 1 >= 0:\n\t\t\t\tt |= dp[i][j - 1]\n\t\t\tdp[i][j] |= t << x | t >> x\n\tfor (i, s) in enumerate(bin(dp[-1][-1])[-ofs - 1:]):\n\t\tif s == '1':\n\t\t\tprint(i)\n\t\t\treturn\nINF = float('inf')\nMOD = 10 ** 9 + 7\nresolve()\n", "import sys\n\ndef main():\n\tinput = sys.stdin.readline\n\t(h, w) = map(int, input().split())\n\ta = [list(map(int, input().split())) for _ in range(h)]\n\tb = [list(map(int, input().split())) for _ in range(h)]\n\tm = 80 * 162\n\tflg = (1 << m * 2) - 1\n\tdp = [[0] * w for j in range(h)]\n\tdp[0][0] |= 1 << a[0][0] - b[0][0] + m\n\tdp[0][0] |= 1 << b[0][0] - a[0][0] + m\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tif i < h - 1:\n\t\t\t\tne = abs(a[i + 1][j] - b[i + 1][j])\n\t\t\t\tdp[i + 1][j] |= dp[i][j] << ne & flg\n\t\t\t\tdp[i + 1][j] |= dp[i][j] >> ne & flg\n\t\t\tif j < w - 1:\n\t\t\t\tne = abs(a[i][j + 1] - b[i][j + 1])\n\t\t\t\tdp[i][j + 1] |= dp[i][j] << ne & flg\n\t\t\t\tdp[i][j + 1] |= dp[i][j] >> ne & flg\n\tans = 10 ** 10\n\tfor i in range(160 * 162):\n\t\tif dp[h - 1][w - 1] >> i & 1:\n\t\t\tans = min(ans, abs(i - m))\n\treturn print(ans)\nmain()\n", "def resolve():\n\t(H, W) = list(map(int, input().split()))\n\tA = [tuple(map(int, input().split())) for _ in range(H)]\n\tB = [tuple(map(int, input().split())) for _ in range(H)]\n\tSub = [[0] * W for i in range(H)]\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tSub[i][j] = abs(A[i][j] - B[i][j])\n\tmax_k = 80 * (H + W)\n\tdp = [[0] * W for _ in range(H)]\n\tdp[0][0] = 1 << max_k + Sub[0][0] | 1 << max_k - Sub[0][0]\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\td = Sub[i][j]\n\t\t\tif i:\n\t\t\t\tdp[i][j] |= dp[i - 1][j] << d | dp[i - 1][j] >> d\n\t\t\tif j:\n\t\t\t\tdp[i][j] |= dp[i][j - 1] << d | dp[i][j - 1] >> d\n\tans = 10 ** 18\n\tfor i in range(max_k * 2 + 1):\n\t\tif dp[H - 1][W - 1] & 1 << i:\n\t\t\tans = min(ans, abs(max_k - i))\n\tprint(ans)\n\ndef __starting_point():\n\tresolve()\n__starting_point()\n", "import sys\ninput = sys.stdin.readline\nMI = lambda : map(int, input().split())\nLI = lambda : list(map(int, input().split()))\n(H, W) = MI()\nA = [LI() for _ in [0] * H]\nB = [LI() for _ in [0] * H]\nG = [[set() for i in range(W)] for j in range(H)]\nG[0][0].add(0)\nfor h in range(H):\n\tfor w in range(W):\n\t\td = A[h][w] - B[h][w]\n\t\tfor a in G[h][w]:\n\t\t\tif h != H - 1:\n\t\t\t\tG[h + 1][w].add(abs(a + d))\n\t\t\t\tG[h + 1][w].add(abs(a - d))\n\t\t\tif w != W - 1:\n\t\t\t\tG[h][w + 1].add(abs(a + d))\n\t\t\t\tG[h][w + 1].add(abs(a - d))\nres = set()\nd = A[H - 1][W - 1] - B[H - 1][W - 1]\nfor a in G[H - 1][W - 1]:\n\tres.add(abs(a + d))\n\tres.add(abs(a - d))\nres = sorted(list(res))\nprint(min(res))\n", "from collections import deque\n(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nC = [[0] * W for _ in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tC[i][j] = abs(A[i][j] - B[i][j])\nM = 80 * (H + W)\ndp = [[0 for i in range(W)] for j in range(H)]\nc = C[0][0]\ndp[0][0] += 1 << c + M | 1 << M - c\nfor s in range(1, H + W):\n\tfor b in range(max(s - H + 1, 0), min(s + 1, W)):\n\t\ta = s - b\n\t\tc = C[a][b]\n\t\tif a >= 1:\n\t\t\td = dp[a - 1][b]\n\t\t\tdp[a][b] |= d << c | d >> c\n\t\tif b >= 1:\n\t\t\td = dp[a][b - 1]\n\t\t\tdp[a][b] |= d << c | d >> c\nans = 10 ** 10\nd = dp[-1][-1]\nfor i in range(0, M * 2 + 1):\n\tif 1 << i & d:\n\t\tans = min(ans, abs(i - M))\nprint(ans)\n", "import numpy as np\nimport itertools\n(H, W) = list(map(int, input().split()))\nA = [tuple(map(int, input().split())) for _ in range(H)]\nB = [tuple(map(int, input().split())) for _ in range(H)]\nD = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]\nmax_num = 80 * (H + W)\ntable = np.zeros((H, W, max_num), dtype='bool')\ntable[0][0][D[0][0]] = True\nit = itertools.product(list(range(H)), list(range(W)))\nnext(it)\nfor (h, w) in it:\n\td = D[h][w]\n\ttable[h][w][d:] += table[h - 1][w][:max_num - d] + table[h][w - 1][:max_num - d]\n\ttable[h][w][:max_num - d] += table[h - 1][w][d:] + table[h][w - 1][d:]\n\ttable[h][w][d:0:-1] += table[h - 1][w][:d] + table[h][w - 1][:d]\nprint(np.amin(*np.where(table[H - 1][W - 1])))\n", "import sys\nreader = (s.rstrip() for s in sys.stdin)\ninput = reader.__next__\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\nma = 80 * 80 + 2\nDP = [[[0] * ma for i in range(w)] for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tk = abs(a[i][j] - b[i][j])\n\t\tif i == 0 and j == 0:\n\t\t\tDP[i][j][k] = 1\n\t\t\tcontinue\n\t\telse:\n\t\t\tup = min((i + j + 1) * 80 + 1, ma - k)\n\t\t\tfor l in range(up):\n\t\t\t\tDP[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]\nfor i in range(ma):\n\tif DP[-1][-1][i]:\n\t\tprint(i)\n\t\texit()\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\npos = 160 * 80\ndp = [[0] * w for i in range(h)]\nsub = abs(a[0][0] - b[0][0])\ndp[0][0] = 1 << pos - sub | 1 << pos + sub\nfor c in range(h):\n\tfor l in range(w):\n\t\tsub = abs(a[c][l] - b[c][l])\n\t\tif l != 0 and c != 0:\n\t\t\tdp[c][l] |= dp[c][l - 1] << sub | dp[c][l - 1] >> sub | dp[c - 1][l] << sub | dp[c - 1][l] >> sub\n\t\telif c != 0:\n\t\t\tdp[c][l] |= dp[c - 1][l] << sub | dp[c - 1][l] >> sub\n\t\telif l != 0:\n\t\t\tdp[c][l] |= dp[c][l - 1] << sub | dp[c][l - 1] >> sub\nbit = dp[-1][-1]\nfor i in range(pos):\n\tif bit & 1 << pos + i or bit & 1 << pos - i:\n\t\tprint(i)\n\t\tbreak\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\ndp = [[set() for _ in range(W)] for _ in range(H)]\ndp[0][0].add(0)\nfor i in range(W + H - 1):\n\t(I, J) = (0, 0)\n\tif i < H:\n\t\tI = i\n\t\tJ = 0\n\telse:\n\t\tI = H - 1\n\t\tJ = i - H + 1\n\twhile I >= 0 and J < W:\n\t\tsa = abs(A[I][J] - B[I][J])\n\t\tfor point in dp[I][J]:\n\t\t\tif I != H - 1:\n\t\t\t\tdp[I + 1][J].add(point + sa)\n\t\t\t\tdp[I + 1][J].add(abs(point - sa))\n\t\t\tif J != W - 1:\n\t\t\t\tdp[I][J + 1].add(point + sa)\n\t\t\t\tdp[I][J + 1].add(abs(point - sa))\n\t\tI -= 1\n\t\tJ += 1\nans = dp[H - 1][W - 1]\nsa = abs(A[H - 1][W - 1] - B[H - 1][W - 1])\nres = float('inf')\nfor p in ans:\n\tres = min(res, abs(p + sa), abs(p - sa))\nprint(res)\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\ndp = [[0] * (W + 1) for _ in range(H + 1)]\nF = 80 * 200 + 100\ndp[0][0] = 1 << F\nfor h in range(H):\n\tfor w in range(W):\n\t\ta = A[h][w]\n\t\tb = B[h][w]\n\t\td = dp[h][w]\n\t\tdp[h + 1][w] |= d << abs(a - b) | d >> abs(a - b)\n\t\tdp[h][w + 1] |= d << abs(a - b) | d >> abs(a - b)\nres = dp[H][W - 1] | dp[H - 1][W]\nans = 10 ** 18\nfor d in range(F * 2):\n\tif res & 1 << d != 0:\n\t\tans = min(ans, abs(d - F))\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\nD = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]\n\ndef cal():\n\tdp1 = [set() for _ in range(W)]\n\tdp2 = [set() for _ in range(W)]\n\tfor h in range(H):\n\t\tfor w in range(W):\n\t\t\td = D[h][w]\n\t\t\tif h == 0 and w == 0:\n\t\t\t\tdp2[0].add(d)\n\t\t\tfor v in dp1[w]:\n\t\t\t\tv1 = v + d\n\t\t\t\tv2 = v - d if v >= d else -v + d\n\t\t\t\tdp2[w].add(v1)\n\t\t\t\tdp2[w].add(v2)\n\t\t\tif 0 < w:\n\t\t\t\tfor v in dp2[w - 1]:\n\t\t\t\t\tv1 = v + d\n\t\t\t\t\tv2 = v - d if v >= d else -v + d\n\t\t\t\t\tdp2[w].add(v1)\n\t\t\t\t\tdp2[w].add(v2)\n\t\tdp1 = dp2\n\t\tdp2 = [set() for _ in range(W)]\n\treturn min(dp1[W - 1])\nans = cal()\nprint(ans)\n", "import numpy as np\n(H, W) = list(map(int, input().split()))\nAs = [list(map(int, input().split())) for _ in range(H)]\nBs = [list(map(int, input().split())) for _ in range(H)]\nds = [[abs(A - B) for (A, B) in zip(row_A, row_B)] for (row_A, row_B) in zip(As, Bs)]\nsize = 10005\ndp = np.full((H, W, size), False)\ndp[0][0][ds[0][0]] = True\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i + 1 < H:\n\t\t\td = ds[i + 1][j]\n\t\t\tdp[i + 1][j][d:] = np.logical_or(dp[i][j][:size - d], dp[i + 1][j][d:])\n\t\t\tdp[i + 1][j][:size - d] = np.logical_or(dp[i][j][d:], dp[i + 1][j][:size - d])\n\t\t\tdp[i + 1][j][:d + 1] = np.logical_or(dp[i][j][d::-1], dp[i + 1][j][:d + 1])\n\t\tif j + 1 < W:\n\t\t\td = ds[i][j + 1]\n\t\t\tdp[i][j + 1][d:] = np.logical_or(dp[i][j][:size - d], dp[i][j + 1][d:])\n\t\t\tdp[i][j + 1][:size - d] = np.logical_or(dp[i][j][d:], dp[i][j + 1][:size - d])\n\t\t\tdp[i][j + 1][:d + 1] = np.logical_or(dp[i][j][d::-1], dp[i][j + 1][:d + 1])\nprint(np.min(np.where(dp[-1][-1])))\n", "import numpy as np\n\ndef main():\n\t(h, w) = list(map(int, input().split()))\n\ta = [list(map(int, input().split())) for _ in range(h)]\n\tb = [list(map(int, input().split())) for _ in range(h)]\n\tn = 80 * (80 + 80) + 10\n\tm = n // 2\n\tdp = [[None] * w for i in range(h)]\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tdp[i][j] = np.zeros(n, np.bool)\n\tdp[0][0][m + abs(a[0][0] - b[0][0])] = True\n\tdp[0][0][m - abs(a[0][0] - b[0][0])] = True\n\tfor i in range(h):\n\t\tfor j in range(w):\n\t\t\tx = abs(a[i][j] - b[i][j])\n\t\t\tif 0 < i and 0 < h:\n\t\t\t\tdp[i][j][x:] |= dp[i - 1][j][:n - x]\n\t\t\t\tdp[i][j][:n - x] |= dp[i - 1][j][x:]\n\t\t\t\tdp[i][j][x:] |= dp[i][j - 1][:n - x]\n\t\t\t\tdp[i][j][:n - x] |= dp[i][j - 1][x:]\n\t\t\telif 0 < i:\n\t\t\t\tdp[i][j][x:] |= dp[i - 1][j][:n - x]\n\t\t\t\tdp[i][j][:n - x] |= dp[i - 1][j][x:]\n\t\t\telif 0 < j:\n\t\t\t\tdp[i][j][x:] |= dp[i][j - 1][:n - x]\n\t\t\t\tdp[i][j][:n - x] |= dp[i][j - 1][x:]\n\tans = float('inf')\n\tfor i in range(m - 80 - 1, m + 80 + 2):\n\t\tif dp[h - 1][w - 1][i]:\n\t\t\tans = min(ans, abs(m - i))\n\tprint(ans)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(H, W) = map(int, input().split())\nM = (H + W) * 80\nA = [tuple(map(int, input().split())) for _ in range(H)]\nB = [tuple(map(int, input().split())) for _ in range(H)]\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = 1 << M - abs(A[0][0] - B[0][0])\nfor h in range(H):\n\tfor (w, (a, b)) in enumerate(zip(A[h], B[h])):\n\t\td = abs(a - b)\n\t\tmask = 0\n\t\tif h > 0:\n\t\t\tmask |= dp[h - 1][w] << d\n\t\t\tmask |= dp[h - 1][w] >> d\n\t\tif w > 0:\n\t\t\tmask |= dp[h][w - 1] << d\n\t\t\tmask |= dp[h][w - 1] >> d\n\t\tdp[h][w] |= mask\nstate = dp[-1][-1]\nnums = []\nfor (digit, b) in enumerate(bin(state)[2:][::-1]):\n\tif b == '1':\n\t\tnums.append(digit - M)\nans = min((abs(n) for n in nums))\nprint(ans)\n", "import sys\ninput = sys.stdin.readline\n(h, w) = list(map(int, input().split()))\nla = [list(map(int, input().split())) for i in range(h)]\nfor i in range(h):\n\tl = list(map(int, input().split()))\n\tfor (j, num) in enumerate(l):\n\t\tla[i][j] = abs(la[i][j] - num)\ndp = [[0 for i in range(w)] for j in range(h)]\nk = (h + w) * 80 + 2\ndp[0][0] = 1 << k + la[0][0] | 1 << k - la[0][0]\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i:\n\t\t\tdp[i][j] |= dp[i - 1][j] << la[i][j] | dp[i - 1][j] >> la[i][j]\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << la[i][j] | dp[i][j - 1] >> la[i][j]\ns = bin(dp[-1][-1])[2:]\nl = len(s) - 1\nans = float('inf')\nfor i in range(l, -1, -1):\n\tif s[i] == '1':\n\t\tm = abs(l - i - k)\n\t\tif m < ans:\n\t\t\tans = m\nprint(ans)\n", "def x():\n\treturn map(int, input().split())\nv = list\nc = abs\nr = range\n(h, w) = x()\np = v(r(h))\na = [v(x()) for i in p]\nb = [v(x()) for i in p]\nm = 13120\nD = [[[0] * m for i in r(w)] for i in p]\nfor i in p:\n\tfor j in r(w):\n\t\tk = c(a[i][j] - b[i][j])\n\t\tif i | j:\n\t\t\tfor l in r((i + j + 1) * 80 + 1):\n\t\t\t\te = c(l - k)\n\t\t\t\tD[i][j][l] = D[i][j - 1][e] | D[i][j - 1][l + k] | D[i - 1][j][e] | D[i - 1][j][l + k]\n\t\telse:\n\t\t\tD[i][j][k] = 1\nprint(D[-1][-1].index(1))\n", "def inpl():\n\treturn list(map(int, input().split()))\n(H, W) = inpl()\nA = [inpl() for _ in range(H)]\nB = [inpl() for _ in range(H)]\nDP = [[0 for _ in range(W + 1)] for _ in range(H + 1)]\nDP[0][0] = 1 << 12800\nfor h in range(H):\n\tfor w in range(W):\n\t\td = abs(A[h][w] - B[h][w])\n\t\tDP[h + 1][w] |= DP[h][w] >> d\n\t\tDP[h + 1][w] |= DP[h][w] << d\n\t\tDP[h][w + 1] |= DP[h][w] >> d\n\t\tDP[h][w + 1] |= DP[h][w] << d\nl = 1 << 12800\nr = 1 << 12800\nfor i in range(12801):\n\tif DP[-1][-2] & l | DP[-1][-2] & r:\n\t\tprint(i)\n\t\tbreak\n\tl = l << 1\n\tr = r >> 1\n", "(H, W) = [int(x) for x in input().split()]\nA = [[0] * W for i in range(H)]\nfor c in [1, -1]:\n\tfor i in range(H):\n\t\tarr = [int(x) for x in input().split()]\n\t\tfor j in range(W):\n\t\t\tA[i][j] += arr[j] * c\nM = 160 * 80\ndp = [[0] * W for i in range(H)]\ndp[0][0] = 1 << M\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j]\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1]\n\t\ta = abs(A[i][j])\n\t\tdp[i][j] = dp[i][j] << a | dp[i][j] >> a\nans = M\nfor i in range(2 * M):\n\tif dp[H - 1][W - 1] & 1 << i > 0:\n\t\tans = min(ans, abs(M - i))\nprint(ans)\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\nma = 80 * 2 * 80\nDP = [[0] * w for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tk = abs(a[i][j] - b[i][j])\n\t\tif i | j:\n\t\t\tm = DP[i - 1][j] | DP[i][j - 1]\n\t\telse:\n\t\t\tm = 1 << ma\n\t\tDP[i][j] = m << k | m >> k\nk = 1 << ma\nfor i in range(ma):\n\tif DP[-1][-1] & k >> i or DP[-1][-1] & k << i:\n\t\tprint(i)\n\t\texit()\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) + [0] for i in range(h)] + [[0] * (w + 1)]\nb = [list(map(int, input().split())) + [0] for i in range(h)] + [[0] * (w + 1)]\ndiff = [[abs(x - y) for (x, y) in zip(i, j)] for (i, j) in zip(a, b)]\ndp = [[0 for j in range(w + 1)] for i in range(h + 1)]\ndp[0][0] = 1 << diff[0][0]\n\ndef reverse(d, x):\n\tres = 0\n\tfor i in range(x + 1):\n\t\tres <<= 1\n\t\tif 1 << i & d:\n\t\t\tres |= 1\n\treturn res\nfor i in range(h):\n\tfor j in range(w):\n\t\tdp[i][j + 1] |= dp[i][j] << diff[i][j + 1]\n\t\tdp[i][j + 1] |= dp[i][j] >> diff[i][j + 1]\n\t\tdp[i][j + 1] |= reverse(dp[i][j], diff[i][j + 1])\n\t\tdp[i + 1][j] |= dp[i][j] << diff[i + 1][j]\n\t\tdp[i + 1][j] |= dp[i][j] >> diff[i + 1][j]\n\t\tdp[i + 1][j] |= reverse(dp[i][j], diff[i + 1][j])\nlast = dp[h - 1][w - 1]\nfor i in range(6401):\n\tif last >> i & 1:\n\t\tans = i\n\t\tbreak\nprint(ans)\n", "import sys\nINF = float('inf')\n\ndef solve(H: int, W: int, A: 'List[List[int]]', B: 'List[List[int]]'):\n\tbase = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]\n\tmx = (1 << 12800) - 1\n\ttable = [[0] * W for _ in range(H)]\n\ttable[0][0] = 1 << 6400 + base[0][0] | 1 << 6400 - base[0][0]\n\tfor h in range(H):\n\t\tfor w in range(W):\n\t\t\tif h > 0:\n\t\t\t\ttable[h][w] |= table[h - 1][w] << base[h][w]\n\t\t\t\ttable[h][w] |= table[h - 1][w] >> base[h][w]\n\t\t\tif w > 0:\n\t\t\t\ttable[h][w] |= table[h][w - 1] << base[h][w]\n\t\t\t\ttable[h][w] |= table[h][w - 1] >> base[h][w]\n\t\t\ttable[h][w] &= mx\n\tm = INF\n\tfor j in range(12800):\n\t\ti = table[H - 1][W - 1] >> j & 1\n\t\tif i == 1:\n\t\t\tm = min(m, abs(j - 6400))\n\tprint(m)\n\treturn\n\ndef main():\n\n\tdef iterate_tokens():\n\t\tfor line in sys.stdin:\n\t\t\tfor word in line.split():\n\t\t\t\tyield word\n\ttokens = iterate_tokens()\n\tH = int(next(tokens))\n\tW = int(next(tokens))\n\tA = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]\n\tB = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]\n\tsolve(H, W, A, B)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\ns = [0] * w\ns[0] = p = 1 << 6400\nfor i in range(h):\n\tfor j in range(w):\n\t\td = abs(a[i][j] - b[i][j])\n\t\tif j > 0:\n\t\t\ts[j] |= s[j - 1]\n\t\ts[j] = s[j] << d | s[j] >> d\nt = s[-1]\nfor i in range(6401):\n\tif t & p << i or t & p >> i:\n\t\tprint(i)\n\t\tbreak\n", "import sys\ninput = sys.stdin.readline\n(H, W) = list(map(int, input().split()))\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\nD = [[0] * W for i in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tD[i][j] = abs(A[i][j] - B[i][j])\nbuf = 80 * (H + W)\ndp = [[0] * W for i in range(H)]\ndp[0][0] = 1 << buf + D[0][0] | 1 << buf - D[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\td = D[i][j]\n\t\tif i:\n\t\t\tdp[i][j] |= dp[i - 1][j] << d | dp[i - 1][j] >> d\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << d | dp[i][j - 1] >> d\nans = 10 ** 18\nfor i in range(buf * 2 + 1):\n\tif dp[H - 1][W - 1] & 1 << i:\n\t\tans = min(ans, abs(buf - i))\nprint(ans)\n", "import numpy as np\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\nd = []\nfor i in range(h):\n\td.append([abs(a[i][j] - b[i][j]) for j in range(w)])\ndp = np.zeros((h, w, 12800))\ndp[0, 0, d[0][0] + 6400] = 1\nfor i in range(w - 1):\n\tif d[0][i + 1] == 0:\n\t\tdp[0, i + 1] += dp[0, i]\n\t\tcontinue\n\tdp[0, i + 1, d[0][i + 1]:] += dp[0, i, :-d[0][i + 1]]\n\tdp[0, i + 1, :-d[0][i + 1]] += dp[0, i, d[0][i + 1]:]\nfor i in range(h - 1):\n\tif d[i + 1][0] == 0:\n\t\tdp[i + 1, 0] += dp[i, 0]\n\t\tcontinue\n\tdp[i + 1, 0, d[i + 1][0]:] += dp[i, 0, :-d[i + 1][0]]\n\tdp[i + 1, 0, :-d[i + 1][0]] += dp[i, 0, d[i + 1][0]:]\nfor r in range(1, h):\n\tfor c in range(1, w):\n\t\tif d[r][c] == 0:\n\t\t\tdp[r, c] += dp[r - 1, c]\n\t\t\tdp[r, c] += dp[r, c - 1]\n\t\t\tcontinue\n\t\tdp[r, c, d[r][c]:] += dp[r - 1, c, :-d[r][c]]\n\t\tdp[r, c, :-d[r][c]] += dp[r - 1, c, d[r][c]:]\n\t\tdp[r, c, d[r][c]:] += dp[r, c - 1, :-d[r][c]]\n\t\tdp[r, c, :-d[r][c]] += dp[r, c - 1, d[r][c]:]\nprint(min([abs(e - 6400) for e in np.where(dp[h - 1, w - 1] > 0)[0]]))\n", "import sys\nimport math\nimport bisect\nimport heapq\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\n\ndef main():\n\t(H, W) = map(int, input().split())\n\tA = [[0] * W for _ in range(H)]\n\tfor i in range(H):\n\t\ta = list(map(int, input().split()))\n\t\tA[i] = a\n\tfor i in range(H):\n\t\tb = list(map(int, input().split()))\n\t\tfor j in range(W):\n\t\t\tA[i][j] -= b[j]\n\tdp = [[set() for i in range(W)] for i in range(H)]\n\tdp[0][0].add(A[0][0])\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tif i != 0:\n\t\t\t\tfor k in dp[i - 1][j]:\n\t\t\t\t\tdp[i][j].add(abs(k - A[i][j]))\n\t\t\t\t\tdp[i][j].add(abs(k + A[i][j]))\n\t\t\tif j != 0:\n\t\t\t\tfor k in dp[i][j - 1]:\n\t\t\t\t\tdp[i][j].add(abs(k - A[i][j]))\n\t\t\t\t\tdp[i][j].add(abs(k + A[i][j]))\n\tprint(min(dp[H - 1][W - 1]))\nmain()\n", "import sys\n\ndef LI():\n\treturn [int(x) for x in sys.stdin.readline().split()]\n\ndef main():\n\t(H, W) = LI()\n\tA = [LI() for _ in range(H)]\n\tB = [LI() for _ in range(H)]\n\tD = [[abs(A[h][w] - B[h][w]) for w in range(W)] for h in range(H)]\n\tdp = [[0] * W for _ in range(H)]\n\tdp[0][0] = 1 << D[0][0] << 20000\n\tfor h in range(H):\n\t\tfor w in range(W):\n\t\t\tif h > 0:\n\t\t\t\tdp[h][w] |= dp[h - 1][w] << D[h][w]\n\t\t\t\tdp[h][w] |= dp[h - 1][w] >> D[h][w]\n\t\t\tif w > 0:\n\t\t\t\tdp[h][w] |= dp[h][w - 1] << D[h][w]\n\t\t\t\tdp[h][w] |= dp[h][w - 1] >> D[h][w]\n\tfor i in range(81):\n\t\tbit = 1 << 20000 + i\n\t\tbit |= 1 << 20000 - i\n\t\tif dp[H - 1][W - 1] & bit:\n\t\t\treturn i\nprint(main())\n", "(h, w) = map(int, input().split())\nalist = [list(map(int, input().split())) for i in range(h)]\nblist = [list(map(int, input().split())) for i in range(h)]\ndlist = [[0] * w for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tdlist[i][j] = abs(alist[i][j] - blist[i][j])\nl = [[0] * w for i in range(h)]\nl[0][0] = 1 << 80 + dlist[0][0] | 1 << 80 - dlist[0][0]\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i > 0:\n\t\t\tl[i][j] |= l[i - 1][j] << 80 + dlist[i][j]\n\t\t\tl[i][j] |= l[i - 1][j] << 80 - dlist[i][j]\n\t\tif j > 0:\n\t\t\tl[i][j] |= l[i][j - 1] << 80 + dlist[i][j]\n\t\t\tl[i][j] |= l[i][j - 1] << 80 - dlist[i][j]\ndblist = list(bin(l[h - 1][w - 1]))[::-1]\nm = 80 * (h + w - 1)\nans = m\nfor i in range(len(dblist)):\n\tif dblist[i] == '1':\n\t\tans = min(ans, abs(m - i))\nprint(ans)\n", "def main():\n\t(H, W) = [int(i) for i in input().split()]\n\tA = [[int(i) for i in input().split()] for _ in range(H)]\n\tB = [[int(i) for i in input().split()] for _ in range(H)]\n\tM = (H + W) * 80 + 1\n\tu = [[False] * M for _ in range(W)]\n\tv = [[False] * M for _ in range(W)]\n\tF = [False] * M\n\tv[0][0] = True\n\tfor h in range(H):\n\t\t(v, u) = (u, v)\n\t\tvl = F\n\t\tfor w in range(W):\n\t\t\t(a, b) = (A[h][w], B[h][w])\n\t\t\td = a - b if a > b else b - a\n\t\t\tuu = u[w]\n\t\t\tvv = v[w]\n\t\t\tfor i in range(M):\n\t\t\t\tdi = i - d if i > d else d - i\n\t\t\t\tvv[i] = i + d < M and (uu[i + d] or vl[i + d]) or (uu[di] or vl[di])\n\t\t\tvl = vv\n\tva = v[-1]\n\tfor i in range(M):\n\t\tif va[i]:\n\t\t\tprint(i)\n\t\t\treturn\n\traise\nmain()\n", "from sys import stdin\ninput = stdin.buffer.readline\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\ndp = [0] * -~w\ndp[0] = 1 << 6400\nfor i in range(h):\n\tfor j in range(w):\n\t\tt = dp[j]\n\t\tif j:\n\t\t\tt |= dp[j - 1]\n\t\tx = abs(a[i][j] - b[i][j])\n\t\tdp[j] = t << x | t >> x\nfor (i, x) in enumerate(bin(dp[w - 1])[-6401:]):\n\tif int(x):\n\t\tprint(i)\n\t\texit(0)\n", "import sys\ninput = sys.stdin.readline\n(h, w) = list(map(int, input().split()))\nla = [list(map(int, input().split())) for i in range(h)]\nfor i in range(h):\n\tl = list(map(int, input().split()))\n\tfor (j, num) in enumerate(l):\n\t\tla[i][j] = abs(la[i][j] - num)\ndp = [[0 for i in range(w)] for j in range(h)]\nk = (h + w) * 80 + 2\ndp[0][0] = 1 << k + la[0][0] | 1 << k - la[0][0]\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i:\n\t\t\tdp[i][j] |= dp[i - 1][j] << la[i][j] | dp[i - 1][j] >> la[i][j]\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << la[i][j] | dp[i][j - 1] >> la[i][j]\ncheck = dp[-1][-1]\nfor i in range(k):\n\tif check >> k + i & 1 or check >> k - i & 1:\n\t\tprint(i)\n\t\treturn\n", "def solve():\n\tfrom sys import stdin\n\tf_i = stdin\n\t(H, W) = map(int, f_i.readline().split())\n\tA = tuple((tuple(map(int, f_i.readline().split())) for i in range(H)))\n\tB = tuple((tuple(map(int, f_i.readline().split())) for i in range(H)))\n\tdp1 = [0] * W\n\tbit_width = 80 * (H + W - 2)\n\tdp1[0] = 1 << bit_width\n\tfor (A_i, B_i) in zip(A, B):\n\t\tdp2 = [0] * W\n\t\tdiff = abs(A_i[0] - B_i[0])\n\t\tdp2[0] = dp1[0] << diff | dp1[0] >> diff\n\t\tfor (j, t) in enumerate(zip(A_i[1:], B_i[1:]), start=1):\n\t\t\t(A_ij, B_ij) = t\n\t\t\tdiff = abs(A_ij - B_ij)\n\t\t\tb = dp1[j] | dp2[j - 1]\n\t\t\tdp2[j] = b << diff | b >> diff\n\t\tdp1 = dp2\n\tb = bin(dp2[-1])\n\tb = b[-bit_width - 1:]\n\tprint(b.index('1'))\nsolve()\n", "import numpy as np\nimport itertools\n(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H * 2)]\nM = [[abs(A[i][j] - A[H + i][j]) for j in range(W)] for i in range(H)]\nm = max((max((j for j in i)) for i in M))\nr = m * (H + W) + 1\ndp = np.zeros((H, W, r), dtype='bool')\ndp[0][0][M[0][0]] = True\nit = itertools.product(range(H), range(W))\nnext(it)\nfor (h, w) in it:\n\tm = M[h][w]\n\tdp[h][w][m:] |= dp[h][w - 1][:r - m] | dp[h - 1][w][:r - m]\n\tdp[h][w][:r - m] |= dp[h][w - 1][m:] | dp[h - 1][w][m:]\n\tdp[h][w][:m] |= dp[h][w - 1][m:0:-1] | dp[h - 1][w][m:0:-1]\nfor i in range(r):\n\tif dp[-1][-1][i]:\n\t\tprint(i)\n\t\tbreak\n", "import numpy as np\n(H, W) = map(int, input().split())\nA = np.zeros((H, W))\nfor c in [1, -1]:\n\tfor i in range(H):\n\t\tnum = list(map(int, input().split()))\n\t\tA[i, :] += np.array(num) * c\nM = 160 * 80\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = 1 << M\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j]\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1]\n\t\ta = abs(A[i, j])\n\t\tdp[i][j] = dp[i][j] << int(a) | dp[i][j] >> int(a)\ni = M\nwhile True:\n\tif dp[H - 1][W - 1] >> i & 1:\n\t\tprint(i - M)\n\t\tbreak\n\ti += 1\n", "import sys\ninput = sys.stdin.readline\n(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\nab = [[0] * w for _ in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tab[i][j] = abs(a[i][j] - b[i][j])\nm = 12800\ndp = [[0] * w for _ in range(h)]\ndp[0][0] = 1 << m + ab[0][0] | 1 << m - ab[0][0]\nfor i in range(h):\n\tfor j in range(w):\n\t\tfor (dx, dy) in [(1, 0), (0, 1)]:\n\t\t\t(nx, ny) = (i + dx, j + dy)\n\t\t\tif 0 <= nx < h and 0 <= ny < w:\n\t\t\t\tdp[nx][ny] = dp[nx][ny] | dp[i][j] << ab[nx][ny]\n\t\t\t\tdp[nx][ny] = dp[nx][ny] | dp[i][j] >> ab[nx][ny]\nfor i in range(m + 1):\n\tif dp[h - 1][w - 1] >> i & 1:\n\t\tans = m - i\nprint(ans)\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for _ in range(H)]\nB = [list(map(int, input().split())) for _ in range(H)]\ndp = [[0 for _ in range(W)] for _ in range(H)]\nSIZE = 20000\nD = abs(A[0][0] - B[0][0])\ndp[0][0] = 1 << SIZE - D | 1 << SIZE + D\nfor i in range(H):\n\tfor j in range(W):\n\t\tD = abs(A[i][j] - B[i][j])\n\t\tdp[i][j] |= dp[i - 1][j] << D | dp[i - 1][j] >> D\n\t\tdp[i][j] |= dp[i][j - 1] << D | dp[i][j - 1] >> D\nfor i in range(SIZE):\n\tif dp[-1][-1] >> SIZE + i & 1:\n\t\tprint(i)\n\t\texit()\n", "(H, W) = map(int, input().split())\nA = [list(map(int, input().split())) for i in range(H)]\nB = [list(map(int, input().split())) for i in range(H)]\ncenter = 80 * (H + W)\nC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\ndp = [[0] * W for i in range(H)]\ndp[0][0] = 1 << center + C[0][0] | 1 >> center - C[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i:\n\t\t\tdp[i][j] |= dp[i - 1][j] << C[i][j]\n\t\t\tdp[i][j] |= dp[i - 1][j] >> C[i][j]\n\t\tif j:\n\t\t\tdp[i][j] |= dp[i][j - 1] << C[i][j]\n\t\t\tdp[i][j] |= dp[i][j - 1] >> C[i][j]\nans = center * 2\nfor i in range(center * 2):\n\tif dp[H - 1][W - 1] >> i & 1:\n\t\tans = min(ans, abs(i - center))\nprint(ans)\n", "import numpy as np\n(H, W, *L) = map(int, open(0).read().split())\nA = L[:H * W]\nB = L[H * W:]\nC = [abs(b - a) for (a, b) in zip(A, B)]\nU = max(C) * (H + W)\nN = 2 * U + 1\nINF = 10 ** 10\ndp = np.zeros((H, W, N), dtype=bool)\ndp[0, 0, C[0] + U] = True\nfor i in range(1, W):\n\tc = C[i]\n\tdp[0, i, c:] |= dp[0, i - 1, :N - c]\n\tdp[0, i, :N - c] |= dp[0, i - 1, c:]\nfor i in range(1, H):\n\tc = C[i * W]\n\tdp[i, 0, c:] |= dp[i - 1, 0, :N - c]\n\tdp[i, 0, :N - c] |= dp[i - 1, 0, c:]\nfor i in range(1, H):\n\tfor j in range(1, W):\n\t\tc = C[i * W + j]\n\t\tdp[i, j, c:] |= dp[i, j - 1, :N - c]\n\t\tdp[i, j, :N - c] |= dp[i, j - 1, c:]\n\t\tdp[i, j, c:] |= dp[i - 1, j, :N - c]\n\t\tdp[i, j, :N - c] |= dp[i - 1, j, c:]\nans = np.min(np.abs(np.where(dp[H - 1][W - 1])[0] - U))\nprint(ans)\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for i in range(h)]\nb = [list(map(int, input().split())) for i in range(h)]\nm = 13120\nDP = [[[0] * m for i in range(w)] for i in range(h)]\nfor i in range(h):\n\tfor j in range(w):\n\t\tk = abs(a[i][j] - b[i][j])\n\t\tif i == 0 and j == 0:\n\t\t\tDP[i][j][k] = 1\n\t\telse:\n\t\t\tfor l in range((i + j + 1) * 80 + 1):\n\t\t\t\tDP[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]\nprint(DP[-1][-1].index(1))\n", "(H, W) = map(int, input().split())\nA = tuple((tuple(map(int, input().split())) for _ in range(H)))\nB = tuple((tuple(map(int, input().split())) for _ in range(H)))\ntable = [0] * W\ntable[0] = 1 << 6400\nfor i in range(H):\n\tfor j in range(W):\n\t\tshamt = abs(A[i][j] - B[i][j])\n\t\tif j > 0:\n\t\t\ttable[j] |= table[j - 1]\n\t\ttable[j] = table[j] << shamt | table[j] >> shamt\ndl = dr = 1 << 6400\nfor i in range(6401):\n\tif table[W - 1] & (dl | dr):\n\t\tprint(i)\n\t\tbreak\n\tdl <<= 1\n\tdr >>= 1\n", "(H, W) = map(int, input().split())\n(A, B) = ([], [])\nfor i in range(H):\n\tX = list(map(int, input().split()))\n\tA.append(X)\nfor i in range(H):\n\tX = list(map(int, input().split()))\n\tB.append(X)\nC = []\nm = 0\nfor i in range(H):\n\tD = []\n\tfor j in range(W):\n\t\tD.append(abs(A[i][j] - B[i][j]))\n\t\tm += abs(A[i][j] - B[i][j])\n\tC.append(D)\ndp = [[set() for i in range(W)] for i in range(H)]\ndp[0][0].add(C[0][0])\ndp[0][0].add(-C[0][0])\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i != 0:\n\t\t\tfor k in dp[i - 1][j]:\n\t\t\t\tdp[i][j].add(abs(k - C[i][j]))\n\t\t\t\tdp[i][j].add(abs(k + C[i][j]))\n\t\tif j != 0:\n\t\t\tfor k in dp[i][j - 1]:\n\t\t\t\tdp[i][j].add(abs(k - C[i][j]))\n\t\t\t\tdp[i][j].add(abs(k + C[i][j]))\nprint(min(dp[-1][-1]))\n", "import sys\nimport numpy as np\ninput = sys.stdin.readline\n(h, w) = [int(j) for j in input().split()]\na = []\nb = []\na = [[int(j) for j in input().split()] for i in range(h)]\nb = [[int(j) for j in input().split()] for i in range(h)]\nx = (h + w) * 80\nl = 2 * x + 1\ndp = [[0] * w for i in range(h)]\ndp[0][0] = np.zeros(l, np.bool)\nd = abs(a[0][0] - b[0][0])\ndp[0][0][x + d] = 1\nfor i in range(h):\n\tfor (j, (s, t)) in enumerate(zip(a[i], b[i])):\n\t\tif i == j == 0:\n\t\t\tcontinue\n\t\td = abs(s - t)\n\t\tp = np.zeros(l, np.bool)\n\t\tif i != 0:\n\t\t\tp[d:] |= dp[i - 1][j][:l - d]\n\t\t\tp[:l - d] |= dp[i - 1][j][d:]\n\t\tif j != 0:\n\t\t\tp[d:] |= dp[i][j - 1][:l - d]\n\t\t\tp[:l - d] |= dp[i][j - 1][d:]\n\t\tdp[i][j] = p\nans = np.abs(np.where(dp[-1][-1])[0] - x).min()\nprint(ans)\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\ndp = [w * [0] for _ in range(h)]\ndp[0][0] = 1 << 80 + (a[0][0] - b[0][0]) | 1 << 80 + (b[0][0] - a[0][0])\nfor i in range(h):\n\tfor j in range(w):\n\t\tif i != 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << 80 + (a[i][j] - b[i][j])\n\t\t\tdp[i][j] |= dp[i - 1][j] << 80 + (b[i][j] - a[i][j])\n\t\tif j != 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << 80 + (a[i][j] - b[i][j])\n\t\t\tdp[i][j] |= dp[i][j - 1] << 80 + (b[i][j] - a[i][j])\nans = 1 << 50000\nfor i in range(50000):\n\tif dp[h - 1][w - 1] & 1 << i:\n\t\tans = min(abs(i - (h + w - 1) * 80), ans)\nprint(ans)\n", "(H, W) = list(map(int, input().split()))\namap = [list(map(int, input().split())) for i in range(H)]\nbmap = [list(map(int, input().split())) for i in range(H)]\ndist_map = [[amap[y][x] - bmap[y][x] for x in range(W)] for y in range(H)]\nmid = 80 * 80 * 5 // 2\ndp = [[1 << mid] * W for y in range(H)]\ndp[0][0] = 1 << dist_map[0][0] + mid | 1 << mid - dist_map[0][0]\nfor x in range(1, W):\n\ty = 0\n\td = abs(dist_map[y][x])\n\tdp[y][x] = dp[y][x - 1] << d | dp[y][x - 1] >> d\nfor y in range(1, H):\n\tx = 0\n\td = abs(dist_map[y][x])\n\tdp[y][x] = dp[y - 1][x] << d | dp[y - 1][x] >> d\nfor y in range(1, H):\n\tfor x in range(1, W):\n\t\td = abs(dist_map[y][x])\n\t\tdp[y][x] = dp[y][x - 1] << d | dp[y][x - 1] >> d | (dp[y - 1][x] << d | dp[y - 1][x] >> d)\nans = dp[-1][-1]\nfor i in range(mid + 1):\n\tif ans & 1 << mid - i or ans & 1 << mid + i:\n\t\tprint(i)\n\t\treturn\n", "import sys\ninput = sys.stdin.readline\n(h, w) = map(int, input().split())\na = [tuple(map(int, input().split())) for _ in [0] * h]\nb = [tuple(map(int, input().split())) for _ in [0] * h]\nmid = 1 << 80 * 160\ndp = [[0] * w for _ in [0] * h]\nfor i in range(h):\n\tfor j in range(w):\n\t\tdiff = abs(a[i][j] - b[i][j])\n\t\tnew = 0\n\t\tif i > 0:\n\t\t\tnew |= dp[i - 1][j]\n\t\tif j > 0:\n\t\t\tnew |= dp[i][j - 1]\n\t\tif (i, j) == (0, 0):\n\t\t\tnew = mid\n\t\tdp[i][j] = new << diff | new >> diff\nres = 10 ** 9\np = dp[-1][-1]\nfor i in range(80 * 321):\n\tif p & 1 == 1:\n\t\tres = min(res, abs(80 * 160 - i))\n\tp = p >> 1\nprint(res)\n", "import sys\n\ndef main():\n\tinput = sys.stdin.readline\n\t(H, W) = map(int, input().split())\n\tA = [list(map(int, input().split())) for _ in range(H)]\n\tB = [list(map(int, input().split())) for _ in range(H)]\n\tC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\n\tM = 160 * 80\n\tdp = [[0 for _ in range(W)] for __ in range(H)]\n\tdp[0][0] = 1 << C[0][0] + M\n\tfor i in range(H):\n\t\tfor j in range(W):\n\t\t\tfor (ni, nj) in [(i, j + 1), (i + 1, j)]:\n\t\t\t\tif ni >= H or nj >= W:\n\t\t\t\t\tcontinue\n\t\t\t\tt = C[ni][nj]\n\t\t\t\tdp[ni][nj] |= dp[i][j] << t\n\t\t\t\tdp[ni][nj] |= dp[i][j] >> t\n\ta = dp[H - 1][W - 1]\n\tans = 0\n\twhile True:\n\t\tif a & 1 << M + ans or a & 1 >> M - ans:\n\t\t\tbreak\n\t\tans += 1\n\tprint(ans)\nmain()\n", "(h, w) = map(int, input().split())\na = [list(map(int, input().split())) for _ in range(h)]\nb = [list(map(int, input().split())) for _ in range(h)]\nC = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]\ndp = [[0] * w for i in range(h)]\nofs = 80 * (h + w)\ndp[0][0] = 1 << ofs + C[0][0] | 1 << ofs - C[0][0]\nfor r in range(h):\n\tfor c in range(w):\n\t\tif c > 0:\n\t\t\tdp[r][c] |= dp[r][c - 1] << C[r][c] | dp[r][c - 1] >> C[r][c]\n\t\tif r > 0:\n\t\t\tdp[r][c] |= dp[r - 1][c] << C[r][c] | dp[r - 1][c] >> C[r][c]\ndp[h - 1][w - 1] >>= ofs\nfor i in range(ofs):\n\tif dp[h - 1][w - 1] >> i & 1:\n\t\tprint(i)\n\t\tbreak\n", "import sys\ninput = sys.stdin.readline\n(h, w) = map(int, input().split())\na = []\nfor i in range(h):\n\ts = list(map(int, input().split()))\n\ta.append(s)\nb = []\nfor i in range(h):\n\ts = list(map(int, input().split()))\n\tb.append(s)\ndp = [[0] * w for i in range(h)]\nt = 80 * (h + w)\ndp[0][0] = 2 ** (t + abs(a[0][0] - b[0][0]))\nfor i in range(h):\n\tfor j in range(w):\n\t\tr = abs(a[i][j] - b[i][j])\n\t\tif j > 0:\n\t\t\tdp[i][j] |= dp[i][j - 1] << r | dp[i][j - 1] >> r\n\t\tif i > 0:\n\t\t\tdp[i][j] |= dp[i - 1][j] << r | dp[i - 1][j] >> r\na = dp[h - 1][w - 1] >> t\nm = a & -a\nprint(m.bit_length() - 1)\n", "import sys\nreadline = sys.stdin.readline\n\ndef reverse(d, x):\n\tres = 0\n\tfor i in range(x + 1):\n\t\tres <<= 1\n\t\tif 1 << i & d:\n\t\t\tres |= 1\n\treturn res\n(H, W) = map(int, readline().split())\nA = [list(map(int, readline().split())) for _ in range(H)]\nB = [list(map(int, readline().split())) for _ in range(H)]\nG = [[0] * W for _ in range(H)]\nfor i in range(H):\n\tfor j in range(W):\n\t\tG[i][j] = abs(A[i][j] - B[i][j])\ndp = [[0] * W for _ in range(H)]\ndp[0][0] = 1 << G[0][0]\nfor s in range(H + W - 1):\n\tfor h in range(max(0, s - (W - 1)), 1 + min(s, H - 1)):\n\t\tw = s - h\n\t\td = dp[h][w]\n\t\tif w != W - 1:\n\t\t\tg = G[h][w + 1]\n\t\t\tdp[h][w + 1] |= d << g | d >> g | reverse(d, g)\n\t\tif h != H - 1:\n\t\t\tg = G[h + 1][w]\n\t\t\tdp[h + 1][w] |= d << g | d >> g | reverse(d, g)\nans = dp[H - 1][W - 1]\nans = (-ans & ans).bit_length() - 1\nprint(ans)\n", "def chk(a):\n\tL = []\n\tfor i in range(13000):\n\t\tif a >> i & 1:\n\t\t\tL.append(i)\n\treturn L\n(H, W) = map(int, input().split())\nA = [[int(a) for a in input().split()] for _ in range(H)]\nB = [[int(a) for a in input().split()] for _ in range(H)]\nC = [[A[i][j] - B[i][j] for j in range(W)] for i in range(H)]\nm = (1 << 12800) - 1\nX = [[0] * W for _ in range(H)]\nX[0][0] = 1 << 80 + C[0][0] | 1 << 80 - C[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i:\n\t\t\tX[i][j] |= X[i - 1][j] << 80 + C[i][j] | X[i - 1][j] << 80 - C[i][j]\n\t\tif j:\n\t\t\tX[i][j] |= X[i][j - 1] << 80 + C[i][j] | X[i][j - 1] << 80 - C[i][j]\n\t\tX[i][j] &= m\ns = bin(X[-1][-1] + (1 << 13000))\nmi = 1 << 100\nfor i in range(len(s)):\n\tif s[-i - 1] == '1':\n\t\tmi = min(mi, abs(i - (H + W - 1) * 80))\nprint(mi)\n", "(H, W) = map(int, input().split())\nA = [[int(a) for a in input().split()] for _ in range(H)]\nB = [[int(a) for a in input().split()] for _ in range(H)]\nC = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]\nX = [[0] * W for _ in range(H)]\nofs = 80 * (H + W)\nX[0][0] = 1 << ofs + C[0][0] | 1 << ofs - C[0][0]\nfor i in range(H):\n\tfor j in range(W):\n\t\tif i > 0:\n\t\t\tX[i][j] |= X[i - 1][j] << C[i][j] | X[i - 1][j] >> C[i][j]\n\t\tif j > 0:\n\t\t\tX[i][j] |= X[i][j - 1] << C[i][j] | X[i][j - 1] >> C[i][j]\nfor k in range(ofs):\n\tif X[i][j] >> k + ofs & 1:\n\t\tbreak\nprint(k)\n"]

difficulty: MEDIUM

name: AtCoder Beginner Contest 147 - Balanced Path

source: atcoder

time_limit: 2.0 seconds

memory_limit: 1024.0 megabytes

raw_problem:
配点 : <var>500</var> 点

問題文

縦 <var>H</var> マス、横 <var>W</var> マスのグリッドがあります。上から <var>i</var> 行目、左から <var>j</var> 列目のマスをマス <var>(i,j)</var> と呼びます。

マス <var>(i,j)</var> には <var>2</var> つの数 <var>A_{ij}, B_{ij}</var> が書かれています。

高橋君はまず各マスについて、<var>2</var> つの数の一方を赤く、もう一方を青く塗ります。

そのあと、マス <var>(1,1)</var> からマス <var>(H,W)</var> まで移動します。高橋君は <var>1</var> 回の行動でマス <var>(i,j)</var> からマス <var>(i+1,j)</var> またはマス <var>(i,j+1)</var> に動くことができます。グリッドからはみ出すような移動はできません。

このときの移動経路 (マス <var>(1,1)</var> とマス <var>(H,W)</var> を含む) について、「経路上のマスの赤く塗られた数の和」と「経路上のマスの青く塗られた数の和」の差の絶対値を 偏り と呼ぶことにします。

高橋君は、色の塗り方と移動経路を適切に選ぶことで偏りを小さくしたいです。

偏りの最小値を求めてください。

制約

<var>2 \leq H \leq 80</var>

<var>2 \leq W \leq 80</var>

<var>0 \leq A_{ij} \leq 80</var>

<var>0 \leq B_{ij} \leq 80</var>

入力中のすべての値は整数である。

入力

入力は以下の形式で標準入力から与えられる。

<var>H</var> <var>W</var>
<var>A_{11}</var> <var>A_{12}</var> <var>\ldots</var> <var>A_{1W}</var>
:
<var>A_{H1}</var> <var>A_{H2}</var> <var>\ldots</var> <var>A_{HW}</var>
<var>B_{11}</var> <var>B_{12}</var> <var>\ldots</var> <var>B_{1W}</var>
:
<var>B_{H1}</var> <var>B_{H2}</var> <var>\ldots</var> <var>B_{HW}</var>

出力

偏りの最小値を求めよ。

入力例 1

2 2
1 2
3 4
3 4
2 1

出力例 1

0

次のような塗り分けと移動経路を選択すると、経路上のマスの赤く塗られた数の和は <var>3+3+1=7</var>、経路上のマスの青く塗られた数の和は <var>1+2+4=7</var> となり、偏りを <var>0</var> にできます。

入力例 2

2 3
1 10 80
80 10 1
1 2 3
4 5 6

出力例 2

2

Score : <var>500</var> points

Problem Statement

We have a grid with <var>H</var> horizontal rows and <var>W</var> vertical columns. Let <var>(i,j)</var> denote the square at the <var>i</var>-th row from the top and the <var>j</var>-th column from the left.

The square <var>(i, j)</var> has two numbers <var>A_{ij}</var> and <var>B_{ij}</var> 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 <var>(1, 1)</var> to the square <var>(H, W)</var>. In one move, he can move from a square <var>(i, j)</var> to the square <var>(i+1, j)</var> or the square <var>(i, j+1)</var>. 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 <var>(1, 1)</var> and <var>(H, W)</var>.

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

<var>2 \leq H \leq 80</var>

<var>2 \leq W \leq 80</var>

<var>0 \leq A_{ij} \leq 80</var>

<var>0 \leq B_{ij} \leq 80</var>

All values in input are integers.

Input

Input is given from Standard Input in the following format:

<var>H</var> <var>W</var>
<var>A_{11}</var> <var>A_{12}</var> <var>\ldots</var> <var>A_{1W}</var>
<var>:</var>
<var>A_{H1}</var> <var>A_{H2}</var> <var>\ldots</var> <var>A_{HW}</var>
<var>B_{11}</var> <var>B_{12}</var> <var>\ldots</var> <var>B_{1W}</var>
<var>:</var>
<var>B_{H1}</var> <var>B_{H2}</var> <var>\ldots</var> <var>B_{HW}</var>

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 <var>3+3+1=7</var> and <var>1+2+4=7</var>, respectively, for the unbalancedness of <var>0</var>.

Sample Input 2

2 3
1 10 80
80 10 1
1 2 3
4 5 6

Sample Output 2

2

question:
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$.
![image](1.png)

Sample Input 2
2 3
1 10 80
80 10 1
1 2 3
4 5 6

Sample Output 2
2

data_split: test