Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

tree = [None] * (N + 1)

def parent(n):
    if tree[n] is None:
        return [n, 0]
    p = parent(tree[n][0])
    if p[0] == tree[n][0]:
        return tree[n]
    d = distance_to_root(n)
    tree[n][0] = p[0]
    tree[n][1] = d
    return tree[n]

def distance_to_root(n):
    ret = 0
    nn = n
    while tree[nn] is not None:
        ret += tree[nn][1]
        nn = tree[nn][0]
    return ret

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")



### FIXED CODE ###

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

LRDi = []
for _ in range(M):
    a = list(map(int, input().split()))
    LRDi.append(a)

#tree = [None] * (N + 1)
tree = [[i, 0] for i in range(N + 1)]

def parent(n):
    p = n
    while tree[p][0] != p:
        p = tree[p][0]
    if p == n:
        return tree[n]
    if p == tree[n][0]:
        return tree[n]
    d = distance_to_root(n)
    tree[n][0] = p
    tree[n][1] = d
    return tree[n]

def distance_to_root(n):
    ret = 0
    nn = n
    while tree[nn][0] != nn:
        ret += tree[nn][1]
        nn = tree[nn][0]
    return ret

for l, r, d in LRDi:
    lp = parent(l)
    rp = parent(r)
    if lp[0] != rp[0]:
        rd = distance_to_root(r)
        tree[rp[0]] = [lp[0], lp[1] + d - rd]
    else:
        d1 = distance_to_root(l)
        d2 = distance_to_root(r)
        if d1 + d != d2:
            print("No")
            exit()

print("Yes")
### BUGGY CODE ###

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

dp = [0 for j in range(W + 1)]
for i in range(N):
  w, v = map(int, input().split())
  for wk in range(W, w - 1, -1):
    if dp[wk - w] + v > dp[wk]:
      dp[wk] = dp[wk - w] + v

print(max(dp))

### FIXED CODE ###

def nap(n, cap):
    val = [0] * (cap + 1)
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap, w - 1, -1):
            nv = val[wk - w] + v
            if val[wk] < nv:
                val[wk] = nv
    return max(val)


n, cap = map(int, input().split())
print(nap(n, cap))
### BUGGY CODE ###

def main():

    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))

    # グルーピング
    import copy
    P2 = set(P)
    Group = []
    while len(P2)>0:
        temp = list(P2)[0]
        tempGroup = []
        while temp in P2:
            tempGroup.append(temp)
            P2.remove(temp)
            temp = P[temp-1]
        Group.append(tempGroup)
    Point = []
    for x in Group:
        tempPoint = []
        for p in x:
            tempPoint.append(C[p-1])
        Point.append(tempPoint)

    #print(Group)
    #print(Point)

    max00 = -10**9
    for x in Point:
        sumx = sum(x)
        tempx = copy.copy(x)
        tempx.extend(x)
        lenx = len(x)
        max0 = -10**9
        dp = [0]*lenx
        if sumx <= 0 or K < lenx:
            for i in range(min(lenx-1,K)):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                max0 = max(max0,max(dp))
                #print(dp)
        else:
            K2 = K % lenx
            SN = int(K/lenx)
            for i in range(lenx):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                #print(dp)
                if i < K2:
                    max0 = max(max0,max(dp) + sumx*SN)
                    #print(max0)
                else:
                    max0 = max(max0,max(dp) + sumx*(SN-1))
        max00 = max(max00,max0)
    print(max00)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
 
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))
 
    # グルーピング
    import copy
    P2 = set(P)
    Group = []
    while len(P2)>0:
        temp = list(P2)[0]
        tempGroup = []
        while temp in P2:
            tempGroup.append(temp)
            P2.remove(temp)
            temp = P[temp-1]
        Group.append(tempGroup)
    Point = []
    for x in Group:
        tempPoint = []
        for p in x:
            tempPoint.append(C[p-1])
        Point.append(tempPoint)
 
    #print(Group)
    #print(Point)
 
    max00 = -10**9
    for x in Point:
        sumx = sum(x)
        tempx = copy.copy(x)
        tempx.extend(x)
        lenx = len(x)
        max0 = -10**9
        dp = [0]*lenx
        if sumx <= 0 or K < lenx:
            for i in range(min(lenx-1,K)):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                max0 = max(max0,max(dp))
                #print(dp)
        else:
            K2 = K % lenx
            SN = int(K/lenx)
            for i in range(lenx):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                #print(dp)
                if i < K2:
                    max0 = max(max0,max(dp) + sumx*SN)
                    #print(max0)
                else:
                    max0 = max(max0,max(dp) + sumx*(SN-1))
        max00 = max(max00,max0)
    print(max00)
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

a, b, x = map(int, input().split())
key = 0
count = 0
if a == b:
    if a % x == 0:
        print(1)
        exit()
    else:
        print(0)
        exit()

for i in range(a, b + 1, 1):
    if i % x == 0:
        key = i
        count += 1
        break
ans = count + (b - key) // x
print(ans)

### FIXED CODE ###

a, b, x = map(int, input().split())

big = b // x + 1
small = (a - 1) // x + 1

ans = big - small
if ans < 0:
    ans = 0

print(ans)
### BUGGY CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
dic = collections.Counter(a)
ans = []
for i in range(q):
  b, c = map(int, input().split())
  if b in dic and c in dic:
    dic[c] += dic[b]
    dic.pop(b)
  elif b in dic and c not in dic:
    dic[c] = dic[b]
    dic.pop(b)
  result = 0
  for k, v in dic.items():
    result += k * v
  ans.append(result)
for i in range(q):
  print(ans[i])

### FIXED CODE ###

k = [i for i in range(1, 10 ** 5 + 1)]
v = [0] * (10 ** 5)
dic = {key: val for key, val in zip(k, v)}
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  dic[a[i]] += 1
q = int(input())
ans = [sum(a)]
for i in range(q):
  b, c = map(int, input().split())
  ans.append(ans[-1] + (c - b) * dic[b])
  dic[c] += dic[b]
  dic[b] = 0
for i in range(1, q + 1):
  print(ans[i])
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
s = [input() for i in range(h)]
t = ((0,1),(1,0),(-1,0),(0,-1))
m = 0
for sy in range(h):
    for sx in range(w):
        if s[sy][sx] == "#":
            continue
        q = deque([(0,sy,sx)])
        max_cost = 0
        my,mx = 0,0
        f = [[True]*w for i in range(h)]
        f[sy][sx] = False
        while(q):
            cost,y,x = q.popleft()
            max_cost = max(max_cost,cost)
            f[y][x] = False
            cost += 1
            for i,j in t:
                ny = y+i
                nx = x+j
                if 0 <= ny < h and 0 <= nx < w:
                    if s[ny][nx] == "." and f[ny][nx]:
                        q.append((cost,ny,nx))
        m = max(m,max_cost)
print(m)

### FIXED CODE ###

from collections import deque
from copy import deepcopy

h,w = map(int,input().split())
s = [list(input()) for i in range(h)]
t = ((0,1),(1,0),(-1,0),(0,-1))
m = 0
for sy in range(h):
    for sx in range(w):
        if s[sy][sx] == "#":
            continue
        ss = deepcopy(s)
        ss[sy][sx] = "#"
        q = deque([(0,sy,sx)])
        max_cost = 0
        my,mx = 0,0
        while(q):
            cost,y,x = q.popleft()
            max_cost = max(max_cost,cost)
            cost += 1
            for i,j in t:
                ny = y+i
                nx = x+j
                if 0 <= ny < h and 0 <= nx < w:
                    if ss[ny][nx] == ".":
                        q.append((cost,ny,nx))
                        ss[ny][nx] = "#"
        m = max(m,max_cost)
print(m)
### BUGGY CODE ###

n = int(input())
a = input()
m = n
for i in range(n):
    if m > a[:i].count("W")+a[i:].count("E"):
        m = a[:i].count("W")+a[i:].count("E")
print(m)

### FIXED CODE ###

n = int(input())
a = input()
m = mi= a.count("E")
for i in range(n):
    if a[i] == "W" : m+=1
    else : m-=1
    mi = min(mi,m) 
print(mi)
### BUGGY CODE ###

N = int(input())
S = input()

count = 0
for i in range(1000):
    num = "{:03}".format(i)
    cur_idx = 0
    for c in S:
        if c == num[cur_idx]:
            cur_idx += 1
        if cur_idx == 3:
            count += 1
            break
print(count)

### FIXED CODE ###

N = int(input())
S = list(input())

count = 0
for i in range(1000):
    num = "{:03}".format(i)
    cursor = -1
    ok = True
    for c in num:
        slice = S[cursor + 1:]
        if c not in slice:
            ok = False
            break
        cursor += slice.index(c) + 1
    if ok:
        count += 1

print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(str, input().split()))
from collections import Counter
for k in range(N):
    Alist = A.copy()
    del Alist[k]#k番目のボールを除いたリスト
    C = Counter(Alist)  #カウント辞書
    count = 0
    for i in range(1,N+1):
        count += (C['{}'.format(i)]*(C['{}'.format(i)]-1))/2
    print(int(count))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
from collections import Counter
count = Counter(a)
allcnt = 0
for i in set(a):
    allcnt+= count[i]*(count[i]-1)/2
for i in range(n):
    print(int(allcnt-count[a[i]]+1))
### BUGGY CODE ###

import math

N = int(input())
count = 0
li = [3, 5, 7]

for i in range(300, N+1):
  t = []

  while(True):
    if i % 10 not in li:
      break

    if i % 10 not in t:
      t.append(i % 10)      

    i = math.floor(i / 10)

    if i == 0 and 3 in t and 5 in t and 7 in t:
      count += 1
      break

print(count)

### FIXED CODE ###

N = int(input())
counter = 0

def dfs(cur, use):
  global counter

  if cur > N:
    return

  if use == 0b111:
    counter += 1

  dfs(cur * 10 + 7, use | 0b001)
  dfs(cur * 10 + 5, use | 0b010)
  dfs(cur * 10 + 3, use | 0b100)

dfs(0, 0b000)
print(counter)
### BUGGY CODE ###

import sys
from heapq import *
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n, m, l = map(int, input().split())
    to = defaultdict(list)
    for _ in range(m):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        to[a].append((b, c))
        to[b].append((a, c))
    q = int(input())
    st = []
    idx = [[-1] * n for _ in range(n)]
    qc = [0] * n
    for i in range(q):
        s, t = map(int, input().split())
        s, t = s - 1, t - 1
        idx[s][t] = i
        qc[min(s, t)] += 1

    # for x in idx:
    # print(x)
    # print(qc)

    ans = [-1] * q
    for s in range(n):
        # print(ans)
        cnt = qc[s]
        if cnt == 0: continue
        hp = []
        heappush(hp, (0, -l, s))
        fin = [False] * n
        while cnt > 0 and hp:
            k, g, u = heappop(hp)
            if fin[u]: continue
            fin[u] = True
            g = -g
            i = idx[s][u]
            if i != -1:
                ans[i] = k
                idx[s][u] = -1
                cnt -= 1
            i = idx[u][s]
            if i != -1:
                ans[i] = k
                idx[u][s] = -1
                cnt -= 1
            for ku, c in to[u]:
                if fin[ku]: continue
                if g - c >= 0:
                    heappush(hp, (k, c - g, ku))
                elif l - c>=0:
                    heappush(hp, (k + 1, -l + c, ku))
    print(*ans,sep="\n")

main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n, m, l = map(int, input().split())
    inf = 1001001001
    dist = [[inf] * n for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        a, b = a - 1, b - 1
        dist[a][b] = dist[b][a] = c
    for w in range(n):
        for u in range(n):
            for v in range(n):
                dist[u][v] = min(dist[u][v], dist[u][w] + dist[w][v])
    dist2 = [[inf] * n for _ in range(n)]
    for u in range(n):
        for v in range(n):
            if dist[u][v] <= l: dist2[u][v] = 1
    for w in range(n):
        for u in range(n):
            for v in range(n):
                dist2[u][v] = min(dist2[u][v], dist2[u][w] + dist2[w][v])

    q = int(input())
    for _ in range(q):
        s, t = map(lambda x: int(x) - 1, input().split())
        ans = dist2[s][t]
        if ans == inf:
            print(-1)
        else:
            print(ans - 1)

main()
### BUGGY CODE ###


H,W,M = list(map(int, input().split()))

hw = []
# w = np.zeros(3*10**5,dtype=np.int64)
# h = np.zeros(3*10**5,dtype=np.int64)
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not([i,j] in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)

### FIXED CODE ###

H,W,M = list(map(int, input().split()))

hw = set()
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.add((h_i-1) + (w_j-1)*3*10**6)
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not(i + j*3*10**6 in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)
### BUGGY CODE ###

first_step_string = input()
query_num = int(input())
query_li = list()
for _ in range(query_num):
    query_li.append(input().split())

ans = first_step_string
rev_flag = False
for query in query_li:
    if query[0] == '1':
        rev_flag = not rev_flag
    elif (query[1] == '1' and rev_flag) or (query[1] == '2' and not rev_flag):
        ans += query[2]
    else:
        ans = query[2] + ans

if rev_flag:
    print(ans[::-1])
else:
    print(ans)


### FIXED CODE ###

from collections import deque

s = deque(input())
query_num = int(input())
query_li = list()
for _ in range(query_num):
    query_li.append(input().split())

rev_flag = False
for query in query_li:
    if query[0] == '1':
        rev_flag = not rev_flag
    elif (query[1] == '1' and rev_flag) or (query[1] == '2' and not rev_flag):
        s.append(query[2])
    else:
        s.appendleft(query[2])

if rev_flag:
    print(''.join(deque(reversed(s))))
else:
    print(''.join(s))
### BUGGY CODE ###

#import pysnooper
import os,re,sys,operator,math,heapq,string
from collections import Counter,deque
from operator import itemgetter
from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
from copy import deepcopy

setrecursionlimit(10**6)

def rec(pp,xx):
    for i in range(n):
        if gragh[pp][i]:
            cnt[i]+=xx
            if tree[i]:
                continue
            rec(i,xx)
    return
n,q=map(int,stdin.readline().rstrip().split())
gragh=[[0]*n for _ in range(n)]
cnt=[0]*n
tree=[0]*n
for i in range(n-1):
    a,b=map(int,stdin.readline().rstrip().split())
    tree[a-1],tree[b-1]=0,1
    gragh[a-1][b-1]=1
for i in range(q):
    p,x=map(int,stdin.readline().rstrip().split())
    cnt[p-1]+=x
    rec(p-1,x)
print(*cnt)

### FIXED CODE ###

#import pysnooper
#import os,re,sys,operator,math,heapq,string
#from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
#from copy import deepcopy

setrecursionlimit(10**6)

def rec(pp,xx=-1):
    for i in gragh[pp]:
        if i==xx:
            continue
        ans[i]+=ans[pp]
        rec(i,pp)

n,q=map(int,stdin.readline().rstrip().split())
ans=[0]*n
gragh=[[]*n for _ in range(n)]
for _ in range(n-1):
    a,b=map(int,stdin.readline().rstrip().split())
    a-=1
    b-=1

    gragh[a].append(b)
    gragh[b].append(a)
for _ in range(q):
    p,x=map(int,stdin.readline().rstrip().split())
    ans[p-1]+=x
rec(0)
print(*ans)
### BUGGY CODE ###

n,m=map(int,input().split())
sl=[]
pl=[]
pena=0
ac=0
ac_p=[]
wa={}
for i in range(m):
    #p,s=map(str,input().split())
    li = input().split()
    p=int(li[0])
    s=li[1]
    #p=int(p)
    if s=="WA":
        wa[p]=wa.get(p,0)+1
    else:#もしACなら
        if not p in ac_p:
            ac+=1
            ac_p.append(p)
            pena+=wa.get(p,0)

print("{0} {1}".format(ac,pena))



### FIXED CODE ###

n,m=map(int,input().split())
sl=[]
pl=[]
pena=0
ac=0
ac_p=[]
wa={}
acdic={}

for i in range(m):
    #p,s=map(str,input().split())
    li = input().split()
    p=int(li[0])
    s=li[1]
    #p=int(p)
    if s=="WA":
        wa[p]=wa.get(p,0)+1
    else:#もしACなら
        #acdic[p]=True
        if acdic.get(p,False)==False:
            ac+=1
            acdic[p]=True
            pena+=wa.get(p,0)

print("{0} {1}".format(ac,pena))
### BUGGY CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
AB = []
for a in range(min(K, len(A))):
  for b in range(min(K, len(B))):
    AB.append(A[a] + B[b])
AB = sorted(AB, reverse=True)
ABC = []
for ab in range(min(K, len(AB))):
  for c in range(min(K, len(C))):
    ABC.append(AB[ab] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
  print(ABC[i])

### FIXED CODE ###

X, Y, Z, K = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
C = [int(c) for c in input().split()]
A = sorted(A, reverse=True)
B = sorted(B, reverse=True)
C = sorted(C, reverse=True)
ABC = []
for a in range(len(A)):
    if a+1 > K:
        break
    for b in range(len(B)):
        if b+1 > K:
            break
        elif (a+1)*(b+1) > K:
            break
        for c in range(len(C)):
            if c+1 > K:
                break
            elif (a+1)*(c+1) > K:
                break
            elif (b+1)*(c+1) > K:
                break
            elif (a+1)*(b+1)*(c+1) > K:
                break
            ABC.append(A[a] + B[b] + C[c])
ABC = sorted(ABC, reverse=True)
for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
import fractions

LCM = A[0]
for i in range(1, N):
    LCM = LCM * A[i] // fractions.gcd(LCM, A[i])

ans = 0
for i in range(N):
    ans += LCM//A[i]

print(ans%(10**9+7))

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
g = 1
MOD = 10**9+7
ans = 0

for i in A:
    tmp = g*i//fractions.gcd(g, i) # それまでのLCM
    ans *= tmp//g
    g = tmp
    ans += g//i

print(ans%MOD)
### BUGGY CODE ###

import bisect

N = int(input())
a_list = [int(input()) for i in range(N)]

colors = []
colors.append(a_list[0])
for i in range(1, N):
    a = a_list[i]
    idx = bisect.bisect_left(colors, a)
    if idx == 0:
        colors.insert(0, a)
    else:
        colors[idx-1] = a

print(len(colors))

### FIXED CODE ###

import bisect
from collections import deque

N = int(input())
a_list = [int(input()) for i in range(N)]

colors = deque([])
colors.append(a_list[0])
for i in range(1, N):
    a = a_list[i]
    idx = bisect.bisect_left(colors, a)
    if idx == 0:
        colors.appendleft(a)
    else:
        colors[idx-1] = a

print(len(colors))
### BUGGY CODE ###

import math
N = int(input())
L = list(map(int,input().split()))
B = []
s = 0
for i in range(N-2):
    for k in range(i+1,N-1):
        for _ in range(k+1,N):
            if L[i]-L[k]<L[_] and L[k]-L[i]<L[_] and L[_]<L[i]+L[k]:
                s = (L[i]+L[k]+L[_])/2
                l = math.sqrt(s*(s-L[i])*(s-L[k])*(s-L[_]))
                B.append(l)
k = set(B)
k = list(k)
print(len(k))

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int,input().split()))
L.sort()
sum = 0
for i in range(0,N):
  L_1st= L[i]
  for j in range(i+1,N):
    L_2nd = L[j]
    c_min = L_2nd-L_1st+1
    c_max = L_2nd+L_1st-1
    l = bisect.bisect_left(L,c_min,lo = j+1)
    if l!= N:
      r = bisect.bisect_right(L,c_max,lo = j+1)
      if r:
        r = r-1
        if r>= l:
          sum += r-l+1
print(sum)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = h*w
a = [None]*h
b = [None]*h
for i in range(h):
    a[i] = list(map(int, input().split()))
for i in range(h):
    b[i] = list(map(int, input().split()))
# for i in range(h):
#     for j in range(h):
dp = [[None]*(w) for _ in range(h)]
# mask = 1<<6400

dp[0][0] = set([a[0][0]-b[0][0], b[0][0]-a[0][0]])
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        v =abs(a[i][j]-b[i][j])
        s = set()
        if i>0:
            for item in dp[i-1][j]:
                s.add(item+v)
                s.add(item-v)
        if j>0:
            for item in dp[i][j-1]:
                s.add(item+v)
                s.add(item-v)
        dp[i][j] = s
ans = min(abs(item) for item in dp[h-1][w-1])
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
n = h*w
a = [None]*h
b = [None]*h
for i in range(h):
    a[i] = list(map(int, input().split()))
for i in range(h):
    b[i] = list(map(int, input().split()))
# for i in range(h):
#     for j in range(h):
dp = [[None]*(w) for _ in range(h)]
mask = (1<<12800)-1
m = 6400
dp[0][0] = 1<<(a[0][0]-b[0][0]+m) | 1<<(b[0][0]-a[0][0]+m)
for i in range(h):
    for j in range(w):
        if i==j==0:
            continue
        v = abs(a[i][j]-b[i][j])
        bit = 0
        if i>0:
            bit |= (dp[i-1][j]<<v)&mask
            bit |= (dp[i-1][j]>>v)
        if j>0:
            bit |= (dp[i][j-1]<<v)&mask
            bit |= (dp[i][j-1]>>v)
        dp[i][j] = bit
# ans = min(abs(item) for item in dp[h-1][w-1])
ans = min(abs(val-m) for val in range(12800) if dp[h-1][w-1]>>val&1)
print(ans)
### BUGGY CODE ###

import re

n, q = map(int, input().split())
s = input()
l, r = [], []
for i in range(q):
    ls, rs = map(int, input().split())
    l.append(ls)
    r.append(rs)

for i in range(q):
    prt = s[l[i]-1:r[i]]
    mch = re.findall('AC', prt)
    print(len(mch))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
l, r = [], []
for i in range(q):
    ls, rs = map(int, input().split())
    l.append(ls)
    r.append(rs)

c = [0 for i in range(n)]

for i in range(n-1):
    fnd = 0
    if s[i:i+2] == 'AC':
        fnd = 1
    c[i+1] = c[i]+fnd

for i in range(q):
    print(c[r[i]-1]-c[l[i]-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

x = int(input())
p_L = [i for i in range(100,106)]

max_count = x/100 + 1

def dfs(ans,next,counter):
    global p_L
    global x
    global max_count

    ans += p_L[next]    
    if ans > x:
        return
    if max_count < counter:
        return
    elif ans == x:
        print(1)
        exit()
    
    counter += 1
    for val in range(0,6):
        dfs(ans,val,counter)

counter = 0
for i in range(0,6):
    dfs(0,i,counter)
print(0)

### FIXED CODE ###

x = int(input())

product = list(range(100,105+1))

dp = [0] * 10**6

dp[0] = 1
for i in product:
    dp[i] = 1

for i in range(0,10**5+1):
    for j in product:
        if dp[i] == 1:
            dp[i+j] = 1

print(dp[x])