Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03032 (python)

Fixed submission:
from heapq import heappush, heappop


N, K = map(int, input().split())

V = list(map(int, input().split()))

ans = 0
for back in range(K + 1):
    getV = min(N, K - back)
    for left in range(getV + 1):
        r = getV - left
        S = 0
        hq = []
        for i in range(left):
            heappush(hq, V[i])
            S += V[i]
        for j in range(r):
            heappush(hq, V[N - 1 - j])
            S += V[N - 1 - j]
        for k in range(back):
            if len(hq) > 0 and hq[0] < 0:
                S -= heappop(hq)

        ans = max(ans, S)

print(ans)

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop


N, K = map(int, input().split())

V = list(map(int, input().split()))

ans = 0
for back in range(K + 1):
    for l in range(K - back + 1):
        r = K - back - l
        S = 0
        hq = []
        for i in range(l):
            heappush(hq, V[i])
            S += V[i]
        for j in range(r):
            heappush(hq, V[N - 1 - j])
            S += V[N - 1 - j]
        for k in range(back):
            if len(hq) > 0:
                if hq[0] < 0:
                    S -= heappop(hq)

        ans = max(ans, S)

print(ans)

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop


N, K = map(int, input().split())

V = list(map(int, input().split()))

ans = 0
for back in range(K // 2 + 1):
    for l in range(K - back + 1):
        r = K - back - l
        S = 0
        hq = []
        for i in range(l):
            heappush(hq, V[i])
            S += V[i]
        for j in range(r):
            heappush(hq, V[N - 1 - j])
            S += V[N - 1 - j]
        for k in range(back):
            if len(hq) > 0 and hq[0] < 0:
                S -= heappop(hq)

        ans = max(ans, S)

print(ans)

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop


N, K = map(int, input().split())

V = list(map(int, input().split()))

ans = 0
for back in range(K // 2 + 1):
    for l in range(K - back + 1):
        r = K - back - l
        S = 0
        hq = []
        for i in range(l):
            heappush(hq, V[i])
            S += V[i]
        for j in range(r):
            heappush(hq, V[N - 1 - j])
            S += V[N - 1 - j]
        for k in range(back):
            S -= heappop(hq)

        ans = max(ans, S)

print(ans)
Problem p03044 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(u):
    for v, w in edge[u]:
        if trail[v] is None:
            trail[v] = (trail[u] + w) % 2
            dfs(v)


N = int(input())
trail = [None] * N
edge = [[] for _ in range(N)]

for i in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v, w))
    edge[v].append((u, w))

trail[0] = 0
dfs(0)

for t in trail:
    print(t)

Buggy submission (verdict: Runtime Error):
def dfs(u):
    for v, w in edge[u]:
        if trail[v] is None:
            trail[v] = (trail[u] + w) % 2
            dfs(v)


N = int(input())
trail = [None] * N
edge = [[] for _ in range(N)]

for i in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    w %= 2
    edge[u].append((v, w))
    edge[v].append((u, w))

trail[0] = 0
dfs(0)

for t in trail:
    print(t)
Problem p03078 (python)

Fixed submission:
from heapq import heappush, heappop

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

q = []
x = y = z = 0
heappush(q, (-(A[x] + B[y] + C[z]), (x, y, z)))
done = set((0, 0, 0))
ans = []
for _ in range(K):
    val, (x, y, z) = heappop(q)
    ans.append(-val)
    for i, j, k in [(1, 0, 0), (0, 1, 0), (0, 0, 1)]:
        nx = x + i; ny = y + j; nz = z + k
        if nx < X and ny < Y and nz < Z and (nx, ny, nz) not in done:
            heappush(q, (-(A[nx] + B[ny] + C[nz]), (nx, ny, nz)))
            done.add((nx, ny, nz))

print(*ans, sep='\n')

Buggy submission (verdict: Runtime Error):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

ans = []
for x in range(X):
    for y in range(Y):
        for z in range(Z):
            if (x + 1) * (y + 1) * (z + 1) <= K:
                ans.append(A[x] + B[y] + C[z])
            else:
                break

ans.sort(revere=True)
print(*ans[:K], sep='\n')
Problem p03281 (python)

Fixed submission:
N = int(input())
cnt = 0
for i in range(1, N + 1, 2):
    k = 0
    for j in range(1, i + 1):
        if i % j == 0:
            k += 1
    if k == 8:
        cnt += 1
print(cnt)

Buggy submission (verdict: Runtime Error):
N = int(input())
cnt = 0
for i in range(1, N + 1):
    k = 0
    for j in range(1, N + 1):
        if i % j == 0:
        k += 1
    if k == 8:
        cnt += 1
print(cnt)

Buggy submission (verdict: Runtime Error):
N = int(input())
cnt = 0
for i in range(1, N + 1):
  k = 0
  for j in range(1, N + 1):
   	if i % j == 0:
      k += 1
  if k == 8:
    cnt += 1

print(cnt)
Problem p03353 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(s, pos):
    global N, K
    ns = {}
    if len(A) > K:
        return
    for i in pos:
        ni = i + 1
        if ni < N:
            x = s + S[ni]
            if x in ns:
                ns[x].append(ni)
            else:
                ns[x] = [ni]
    candidate = []
    for x in list(ns.keys()):
        candidate.append((x, ns[x]))
    candidate.sort()
    for c, idx in candidate:
        A.add(c)
        dfs(c, idx)


S = list(input())
N = len(S)
K = int(input())
alpha = [chr(ord('a') + i) for i in range(26)]

A = set()
for c in alpha:
    if len(A) < K:
        pos = []
        for i, s in enumerate(S):
            if c == s:
                A.add(c)
                pos.append(i)
        dfs(c, pos)

A = list(A)
A.sort()
print(A[K - 1])

Buggy submission (verdict: Runtime Error):
def dfs(s):
    global K, cnt, ans, S
    if cnt == K:
        ans = s
        return
    for c in alpha:
        if S.count(s + c) > 0:
            cnt += 1
            dfs(s + c)


S = input()
K = int(input())
cnt = 0
alpha = [chr(ord('a') + i) for i in range(26)]
ans = ''
dfs('')
print(ans)
Problem p03410 (python)

Fixed submission:
def solve():
    # from bisect import bisect_left
    import sys

    N = int(input())
    A = [int(x) for x in sys.stdin.readline().split()]
    B = [int(x) for x in sys.stdin.readline().split()]
    M = max(A) + max(B)
    K = len(bin(M)) - 2
    mask = (1 << K) - 1
    k = K - 1
    T = 1 << k
    ans = 0
    while k >= 0:
        for i in range(N):
            B[i] &= mask
            A[i] &= mask
        B = list(sorted(b & mask for b in B))
        A = list(sorted(a & mask for a in A))
        bit = 0
        T1, T2, T3 = 0, 0, 0
        for a in reversed(A):
            while T1 < N and a + B[T1] < T:
                T1 += 1
            while T2 < N and a + B[T2] < 2 * T:
                T2 += 1
            while T3 < N and a + B[T3] < 3 * T:
                T3 += 1
            # T1 = bisect_left(B, T - a, T1)
            # T2 = bisect_left(B, 2 * T - a, T2)
            # T3 = bisect_left(B, 3 * T - a, T3)
            # T4 = bisect_left(B, 4 * T - a, T4)
            bit += (N - T3) + (T2 - T1)
            bit &= 1
        ans += bit * T
        k -= 1
        T >>= 1
        mask >>= 1

    print(ans)


if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
def solve():
    from bisect import bisect_left

    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    M = max(A) + max(B)
    K = len(bin(M)) - 2
    mask = (1 << K) - 1
    k = K - 1
    T = 1 << k
    ans = 0
    while k >= 0:
        for i in range(N):
            B[i] &= mask
            A[i] &= mask
        B.sort()
        A.sort(revese=True)
        bit = 0
        T1, T2, T3, T4 = 0, 0, 0, 0
        for a in A:
            T1 = bisect_left(B, T - a, T1)
            T2 = bisect_left(B, 2 * T - a, T2)
            T3 = bisect_left(B, 3 * T - a, T3)
            T4 = bisect_left(B, 4 * T - a, T4)
            bit += (T4 - T3) + (T2 - T1)
            bit &= 1
        ans += bit * T
        k -= 1
        T >>= 1
        mask >>= 1

    print(ans)


if __name__ == '__main__':
    solve()
Problem p03452 (python)

Fixed submission:
class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.par_weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            root = self.find(self.parents[x])
            self.par_weight[x] += self.par_weight[self.parents[x]]
            self.parents[x] = root
            return self.parents[x]

    def union(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            self.par_weight[x] = -w
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.par_weight[y] = w

    def weight(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return self.par_weight[x] + self.weight(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.weight(y) - self.weight(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)

Buggy submission (verdict: Runtime Error):
class WeightedUnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
        self.par_weight = [0] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            root = self.find(self.parents[x])
            self.par_weight[x] += self.par_weight[self.parents[x]]
            self.parents[x] = root
            return self.parents[x]

    def union(self, x, y, w):
        w = w + self.weight(x) - self.weight(y)
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            self.par_weight[x] = -w
        else:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            self.par_weight[y] = w

    def weight(self, x):
        if self.parents[x] < 0:
            return 0
        else:
            return self.par_weight[x] + self.weight(self.parents[x])

    def diff(self, x, y):
        if self.find(x) != self.find(y):
            raise Exception('"{}" belongs to a different tree from "{}"'.format(x, y))
        return self.find_position(y) - self.find_position(x)


N, M = map(int, input().split())
uf = WeightedUnionFind(N)
for i in range(M):
    L, R, D = map(int, input().split())
    L -= 1
    R -= 1
    if uf.find(L) == uf.find(R):
        if uf.diff(L, R) != D:
            res = 'No'
            break
    else:
        uf.union(L, R, D)
else:
    res = 'Yes'

print(res)
Problem p03493 (python)

Fixed submission:
s = input()

ans = 0
for i in s:
  ans += int(i)
print(ans)

Buggy submission (verdict: Runtime Error):
def main():
  N = int(input())
  li = list(map(int, input().split()))

  num_of_operation = 0
  
  while True:
    for num in li:
      if num % 2 == 1:
        break
    
    for i in range(N):
      li[i] //= 2
    num_of_operation += 1
  
  print(num_of_operation)

if __name__ == '__main__':
  main()
Problem p03494 (python)

Fixed submission:
def main():
    N = int(input())
    li = list(map(int, input().split()))

    num_of_operation = 0
    is_dividable = True

    while True:
        for num in li:
            if num % 2 != 0:
                is_dividable = False
                break

        if not is_dividable:
            break

        for i in range(N):
            li[i] //= 2
        num_of_operation += 1

    print(num_of_operation)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
  N = int(input())
  li = list(map(int, input().split()))

  num_of_operation = 0
  
  while True:
    for num in li:
      if num % 2 == 1:
        break
    
    for i in xrange(N):
      li[i] /= 2
    num_of_operation += 1
  
  print(num_of_operation)

if __name__ == '__main__':
  main()

Buggy submission (verdict: Runtime Error):
N = input()
li = list(map(int, input().split()))

cnt = 0
while True:
  if 1 in (li % 2):
    break
  else:
    cnt += 1
print(cnt)
Problem p03565 (python)

Fixed submission:
import re


S_ = input()
T = input()

S_ = S_[::-1]
T = T[::-1]

t = ''
for c in T:
    t += '[?' + c + ']'
regex = re.compile(t)

S, cnt = regex.subn(T, S_, count=1)
if cnt:
    S = S.replace('?', 'a')
    print(S[::-1])
else:
    print('UNRESTORABLE')

Buggy submission (verdict: Runtime Error):
S = input()
T = input()

offset = len(S) - len(T)

ans = []
for d in range(offset + 1):
    A = ''
    Td = '?' * d + T
    for i in range(len(S)):
        if i < len(Td) and S[i] != Td[i] and '?' not in [S[i], Td[i]]:
            break
        else:
            c = S[i] if Td[i] == '?' else Td[i]
            A += c
    else:        
        ans.append(A.replace('?', 'a'))

if len(ans):
    ans.sort()
    print(ans[0])
else:
    print('UNRESTORABLE')

Buggy submission (verdict: Runtime Error):
Sx = input()
T = input()

offset = len(Sx) - len(T) + 1
check = [1] * offset

ans = 'UNRESTORABLE'
if len(Sx) >= len(T):
    for d in range(offset):
        for j in range(len(T)):
            check[d] &= (Sx[j + d] == T[j] or Sx[j + d] == '?')
    
    if any(check):
        k = max(k for k, c in enumerate(check) if c)
        ans = ''
        for i in range(len(Sx)):
            if i < k or k + len(T) < i:
                c = Sx[i]
            else:
                c = T[i - k]
            c = 'a' if c == '?' else c

            ans += c

print(ans)
Problem p03579 (python)

Fixed submission:
from collections import Counter
import sys


sys.setrecursionlimit(10 ** 6)


def dfs(x):
    res = True
    for e in edge[x]:
        if color[e] is None:
            color[e] = 0 if color[x] else 1
            res &= dfs(e)
        else:
            if color[e] == color[x]:
                res &= False
            else:
                res &= True
    return res


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    edge[A].append(B)
    edge[B].append(A)

color = [None] * N
color[0] = 0
isBin = dfs(0)

if isBin:
    C = Counter(color)
    print(C[0] * C[1] - M)
else:
    print(N * (N - 1) // 2 - M)

Buggy submission (verdict: Runtime Error):
from collections import Counter


def dfs(x):
    res = True
    for e in edge[x]:
        if color[e] is None:
            color[e] = 0 if color[x] else 1
            res &= dfs(e)
        else:
            if color[e] == color[x]:
                res &= False
            else:
                res &= True
    return res


N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    edge[A].append(B)
    edge[B].append(A)

color = [None] * N
color[0] = 0
isBin = dfs(0)

if isBin:
    C = Counter(color)
    print(C[0] * C[1] - M)
else:
    print(N * (N - 1) // 2 - M)
Problem p03780 (python)

Fixed submission:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()


    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = N
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        n = mid
        dp = [0] * (K + 1)
        dp[0] = 1
        for i in range(N):
            a = A[i]
            if i == n or a >= K:
                continue
            for j in range(K, -1, -1):
                dp[min(K, j + a)] |= dp[j]
        rst = any(dp[k] for k in range(max(0, K - A[n]), K))
        if rst:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Buggy submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = set()
    dp.add(0)
    ans = set(x for x in range(max(0, K - A[n] + 1), K))
    for i in range(N):
        a = A[i]
        if i == n or a >= K:
            continue
        for j in range(K - a - 1, -1, -1):
            if j in dp:
                if j + a in ans:
                    rst = True
                    break
                else:
                    dp.add(j + a)
        else:
            rst = False
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

Buggy submission (verdict: Runtime Error):
def solve(n):
    global N, K
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        a = 0 if i == n else A[i]
        for j in range(K + 1):
            dp[i + 1][min(K, j + a)] |= dp[i][j]
            dp[i + 1][j] |= dp[i][j]
    rst = any(dp[N][k] for k in range(K - A[n], K))
    return rst


N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)
Problem p03855 (python)

Fixed submission:
from collections import Counter


class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, K, L = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for _ in range(K):
    p, q = map(int, input().split())
    uf1.union(p - 1, q - 1)

for _ in range(L):
    r, s = map(int, input().split())
    uf2.union(r - 1, s - 1)

path = [None] * N
for i in range(N):
    path[i] = (uf1.find(i), uf2.find(i))

cnt = Counter(path)
for i in range(N - 1):
    print(cnt[path[i]], end=' ')
print(cnt[path[N - 1]])

Buggy submission (verdict: Runtime Error):
N, K, L = map(int, input().split())
uf = UnionFind(2 * N)
for _ in range(K):
    p, q = map(int, input().split())
    uf.union(p - 1, q - 1)

for _ in range(L):
    r, s = map(int, input().split())
    uf.union(r - 1 + N, s - 1 + N)

ans = [0] * N
for i in range(N):
    cnt = 0
    for j in range(N):
        if uf.find(i) == uf.find(j) and uf.find(i + N) == uf.find(j + N):
            cnt += 1
    ans[i] = cnt

for i in range(N - 1):
    print(ans[i], end=' ')
print(ans[N - 1])
Problem p03998 (python)

Fixed submission:
from collections import deque

Q = [deque() for _ in range(3)]
for i in range(3):
    for s in list(input()):
        Q[i].append(ord(s) - ord('a'))

k = Q[0].popleft()
while len(Q[k]) != 0:
    k = Q[k].popleft()

print('ABC'[k])

Buggy submission (verdict: Runtime Error):
from collections import deque

Q = [deque() for _ in range(3)]
for i in range(3):
    for s in list(input()):
        Q[i].append(ord(s) - ord('a'))

k = Q[0].popleft()
while True:
    k = Q[k].popleft()
    if len(Q[k]) == 0:
        break

print('ABC'[k])
Problem p02760 (python)

Fixed submission:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	A = []
	for i in range(3):
		a = getlist()
		A.append(a)
	bingo = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

	N = int(input())
	for k in range(N):
		b = int(input())
		for i in range(3):
			for j in range(3):
				if A[i][j] == b:
					bingo[i][j] = 1
	
	judge = "No"
	for i in range(3):
		if bingo[i][0] == 1 and bingo[i][1] == 1 and bingo[i][2] == 1:
			judge = "Yes"
	for i in range(3):
		if bingo[0][i] == 1 and bingo[1][i] == 1 and bingo[2][i] == 1:
			judge = "Yes"

	if bingo[0][0] == 1 and bingo[1][1] == 1 and bingo[2][2] == 1:
		judge = "Yes"
	if bingo[2][0] == 1 and bingo[1][1] == 1 and bingo[0][2] == 1:
		judge = "Yes"

	print(judge)

if __name__ == '__main__':
	main()

Buggy submission (verdict: Runtime Error):
60 88 34
92 41 43
65 73 48
10
60
43
88
11
48
73
65
41
92
34
Problem p02839 (python)

Fixed submission:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	H, W = getlist()
	A = []
	for i in range(H):
		a = getlist()
		A.append(a)
	B = []
	for i in range(H):
		b = getlist()
		B.append(b)

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

	# print(C)
	diff = 12800
	DP = [[0] * W for i in range(H)]
	DP[0][0] = (1 << (diff + C[0][0])) | (1 << (diff - C[0][0]))
	for i in range(1, W):
		DP[0][i] = (DP[0][i - 1] << C[0][i]) | (DP[0][i - 1] >> C[0][i])
	for i in range(1, H):
		DP[i][0] = (DP[i - 1][0] << C[i][0]) | (DP[i - 1][0] >> C[i][0])

	for i in range(1, H):
		for j in range(W):
			DP[i][j] |= (DP[i][j - 1] << C[i][j]) | (DP[i][j - 1] >> C[i][j])
			DP[i][j] |= (DP[i - 1][j] << C[i][j]) | (DP[i - 1][j] >> C[i][j])

	ans = INF
	for i in range(25601):
		if DP[-1][-1] & (1 << i) == (1 << i):
			ans = min(ans, abs(diff - i))

	print(ans)

if __name__ == '__main__':
	main()

Buggy submission (verdict: Runtime Error):
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	H, W = getlist()
	A = []
	for i in range(H):
		a = getlist()
		A.append(a)
	B = []
	for i in range(H):
		b = getlist()
		B.append(b)

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

	DP = [[[0] * 12801 for i in range(W)] for j in range(H)]
	DP[0][0][A[0][0] + 6400] = 1
	for i in range(H):
		for j in range(W):
			for k in range(12801):
				if DP[i][j][k] == 1:
					if j < W - 1:
						DP[i][j + 1][k + A[i][j + 1]] = 1
						DP[i][j + 1][k - A[i][j + 1]] = 1
					if i < H - 1:
						DP[i + 1][j][k + A[i + 1][j]] = 1
						DP[i + 1][j][k - A[i + 1][j]] = 1

	ans = 1000000
	for i in range(12801):
		if DP[H - 1][W - 1][i] == 1:
			ans = min(ans, abs(6400 - i))
	print(ans)

if __name__ == '__main__':
	main()