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

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd
 
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10 ** -7
 
def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))
 
def lcm(x, y): return (x * y) // gcd(x, y)
 
 
def gcd_3(x, y, z):
    return gcd(gcd(x, y), z)
 
K = inp()
 
# dic = {} # key: (i, j, k), el: gcd(i, j, k)
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            a = gcd_3(i, j, k)
            if i == j == k:
                ans += a
            elif i == j or j == k:
                ans += a * 3
            else:
                ans += a * 3 * 2
print(ans)

### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10 ** -7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


def gcd_3(x, y, z):
    return gcd(gcd(x, y), z)

K = inp()

dic = {} # key: (i, j, k), el: gcd(i, j, k)
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        tmp = gcd(i, j)
        for k in range(j, K + 1):
            a = gcd(tmp, k)
            if i == j == k:
                ans += a
            elif i == j or j == k:
                ans += a * 3
            else:
                ans += a * 3 * 2
print(ans)
### BUGGY CODE ###

import math
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def ncr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.reverse()

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

ans = []
total = ncr(N, 2)
for i in range(M):
    h = defaultdict(int)
    for k in utf.p.keys():
        h[utf.find(k)] += 1

    now = 0
    for k, v in h.items():
        if v > 1:
            now += ncr(v, 2)
    ans.append(total - now)
    utf.unite(*ab[i])

for v in reversed(ans):
    print(v)

### FIXED CODE ###

from collections import defaultdict
from collections import deque


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


def nc2(n):
    return (n * (n - 1)) >> 1


N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]

utf = UnionFindTree()
for n in range(1, N + 1):
    utf.make(n)

h = {}
ans = deque([])
total = nc2(N)
now = 0
for i in range(M):
    ans.appendleft(total)

    a, b = ab[M - i - 1]
    x, y = utf.find(a), utf.find(b)
    a = utf.unite(x, y)
    if x != y:
        nx, ny = h.get(x, 1), h.get(y, 1)
        n = nx + ny
        total += nc2(nx) + nc2(ny)
        total -= nc2(n)

        h[x] = 1
        h[y] = 1
        h[a] = n

for v in ans:
    print(v)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
a = [[]]
for _ in range(n):
    tmp = [int(x) for x in input().split()]
    a.append(tmp[::-1])

p = [i for i in range(1, n+1)]
c = defaultdict(int)
done = 0
for d in range(1, n*(n-1)//2+1):
    np = []
    for pp in p:
        if len(a[pp]) == 0:
            continue
        x = a[pp].pop()
        l = min(x, pp)
        r = max(x, pp)
        c[l, r] += 1
        if c[l, r] == 2:
            np.append(l)
            np.append(r)
            done += 1
    if done == (n*(n-1)//2):
        print(d)
        exit()
    if len(np) == 0:
        print(-1)
        exit()
    p = np

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = [[]]
for _ in range(n):
    tmp = [int(x) for x in input().split()]
    a.append(tmp[::-1])

p = [i for i in range(1, n+1)]
c = defaultdict(int)
done = 0
for d in range(1, n*(n-1)//2+1):
    np = []
    for pp in p:
        if len(a[pp]) == 0:
            continue
        x = a[pp].pop()
        l = min(x, pp)
        r = max(x, pp)
        c[l, r] += 1
        if c[l, r] == 2:
            np.append(l)
            np.append(r)
            done += 1
    if done == (n*(n-1)//2):
        print(d)
        exit()
    if len(np) == 0:
        print(-1)
        exit()
    p = np
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = [i - 1 for i in map(int, readline().split())]

m = 64
d = [A]
pre = A
for i in range(m):
    current = [pre[pre[j]] for j in range(n)]
    d.append(current)
    pre = current

route = 0
for i in range(m-1, -1, -1):
    if k >= (x := 1 << i):
        route = d[i][route]
        k -= x
print(route+1)


### FIXED CODE ###

import sys

readline = sys.stdin.readline
n, k = map(int, readline().split())
A = list(map(int, readline().split()))

visited = [False] * n
visited[0] = True
l = [1]
while True:
    x = A[l[-1]-1]
    if visited[x-1]:
        break
    l.append(x)
    visited[x-1] = True
# print(l[l.index(x):])
if len(l) > k:
    print(l[k])
else:
    print(l[l.index(x):][(k-l.index(x)) % len(l[l.index(x):])])
### BUGGY CODE ###

n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]

def knapsack01rec(i, j):
    # i = up until item i, j = up until weight j
    if i == 0 or j <= 0:
        return 0

    if dp[i][j] != -1:
        return dp[i][j]

    if weights[i-1] > j:
        # weights[i] doesn't fit in knapsack
        dp[i][j] = knapsack01rec(i-1, j)
    else:
        dp[i][j] = max(
            knapsack01rec(i-1, j),
            knapsack01rec(i-1, j-weights[i-1]) + values[i-1])
    return dp[i][j]

res = knapsack01rec(n, W)
print(res)

### FIXED CODE ###


def knapsack01iter(n, W, weights, values, dp):
    for i in range(1,n+1):
        for j in range(0, W+1):
            if j < weights[i-1]: # if knapsack cannot fit item i
                dp[i][j] = dp[i-1][j]
            elif j >= weights[i-1]: # knapsack can fit item i
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]]+values[i-1])
    
    return dp[-1][-1]
    
    
n,W = [int(x) for x in input().split()]
weights = []
values = []
for i in range(n):
    l = [int(x) for x in input().split()]
    weights += [l[0]]
    values += [l[1]]

# repeatableKnapsack(n, W, weights, values)

# dp = [[-1 for _ in range(W+1)] for _ in range(n+1)]
# res = knapsack01rec(n, W, weights, values, dp, n, W)
# print(dp)
dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
res = knapsack01iter(n, W, weights, values, dp)
# print(dp)
print(res)
### BUGGY CODE ###

s=input()
a=0
b=[s[0]]
for i in range(1,len(s)):
    if b==[]:
        b.append(s[i])
    elif not b[-1]==s[i]:
        a+=2
        b=b[:(len(b)-1)]
    else:
        b.append(s[i])
print(a)

### FIXED CODE ###

s=input()
a=0
b=0
c=0
for i in range(len(s)):
    if c==0:
        b=s[i]
        c+=1
    elif not b==s[i]:
        a+=2
        c-=1
    else:
        b=s[i]
        c+=1
print(a)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
s=[[0 for _ in range(2)] for _ in range(n)]
for i in range(n):
    cnt=0
    now=i
    while True:
        now=(p[now]-1)
        s[i][0]+=c[now]
        cnt+=1
        if now==i:
            break
    s[i][1]=cnt
ans=-(10**16)
for j in range(n):
    if s[j][0]>0 and k//s[j][1]>0: #何回か回る
        cnt1,cnt2=k,k
        a=k//s[j][1] #最大周回数
        score1=(a*s[j][0])
        score2=((a-1)*s[j][0])
        cnt1-=a*s[j][1]
        now=j
        pscore1=0
        pscore_max1=0
        for x in range(cnt1):
            now=(p[now]-1)
            pscore1+=c[now]
            pscore_max1=max(pscore_max1,pscore1)
        score1+=pscore_max1
        now=j
        pscore2=0
        pscore_max2=0
        for y in range(s[j][1]):
            now=(p[now]-1)
            pscore2+=c[now]
            pscore_max2=max(pscore_max2,pscore2)
        score2+=pscore_max2
        score_max=max(score1,score2)
    else:
        now=j
        score=0
        score_max=c[p[now]-1]
        for x in range(min(k,s[j][1])):
            now=(p[now]-1)
            score+=c[now]
            score_max=max(score_max,score)
    ans=max(ans,score_max)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
s=[[0 for _ in range(2)] for _ in range(n)]
for i in range(n):
    cnt=0
    now=i
    while True:
        now=(p[now]-1)
        s[i][0]+=c[now]
        cnt+=1
        if now==i:
            break
    s[i][1]=cnt
ans=-(10**16)
for j in range(n):
    if s[j][0]>0 and k//s[j][1]>0: #何回か回る
        cnt1,cnt2=k,k
        a=k//s[j][1] #最大周回数
        score1=(a*s[j][0])
        score2=((a-1)*s[j][0])
        cnt1-=a*s[j][1]
        now=j
        pscore1=0
        pscore_max1=0
        for x in range(cnt1):
            now=(p[now]-1)
            pscore1+=c[now]
            pscore_max1=max(pscore_max1,pscore1)
        score1+=pscore_max1
        now=j
        pscore2=0
        pscore_max2=0
        for y in range(s[j][1]):
            now=(p[now]-1)
            pscore2+=c[now]
            pscore_max2=max(pscore_max2,pscore2)
        score2+=pscore_max2
        score_max=max(score1,score2)
    else:
        now=j
        score=0
        score_max=c[p[now]-1]
        for x in range(min(k,s[j][1])):
            now=(p[now]-1)
            score+=c[now]
            score_max=max(score_max,score)
    ans=max(ans,score_max)
print(ans)
### BUGGY CODE ###

import numpy as np

power = 1
n = int(input())
tmp = 10 ** 9 + 7

for i in range(n):
    power = power * (i + 1)

print(power % tmp)

### FIXED CODE ###

power = 1
n = int(input())
tmp = 10 ** 9 + 7

for i in range(n):
    power = power * (i + 1) % tmp

print(power)
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
postCenter=dif=0
tmp = sys.maxsize
for i in range(n):
    if tmp > abs(sum(a[:i])-sum(a[i:])):
        tmp = abs(sum(a[:i])-sum(a[i:]))
        if tmp == 0:
            print(tmp)
            exit()
print(tmp)

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
tmp=sys.maxsize
s = sum(a)
t = 0
for i in range(n):
    t += a[i]
    tmp = min(tmp,abs(s-t*2))
print(tmp)
### BUGGY CODE ###

import math

a,b=map(int, input().split())
i=0
for k in range(10**9):
  if abs(a-k)==abs(b-k):
    print(k)
    i=1
    break
if i==0:
    print('IMPOSSIBLE')

### FIXED CODE ###

a,b=map(int, input().split())
print((a+b)//2 if (a+b)%2==0 else 'IMPOSSIBLE')
### BUGGY CODE ###

from collections import OrderedDict
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)

max_b = max(B)
max_c = max(C)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged


summs = []
for a in A[:K]:
    if len(summs) >= K and a + max_b + max_c < summs[K-1]:
        break

    for b in B[:K]:
        if len(summs) >= K and a + b + max_c < summs[K-1]:
            break

        for c in C[:K]:
            summ = a + b + c
            if len(summs) >= K:
                min_sum = summs[K-1]    
                if summ < min_sum:
                    break
            summs.append(summ)
        summs = merge_sort(summs)
        summs.reverse()

for s in summs[0:K]:
    print(s)

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

#D - Div Game
N = int(input())

def Prime_factorize(n):
    cnt = 0
    A = []
    #2の倍数で割っていく
    z = 2
    while n%z==0 and (n>=z):
        cnt += 1
        n //= z
        
        A.append(z)
        #割るたびに2倍
        z *= 2
    #割る始めの数をfとして保持
    f = 3
    z = 3
    #sqrt(n)以内に全ての素因数は含まれる
    while f*2 <= N:
        if n%z == 0:
            cnt += 1
            n //= z
            A.append(z)
            
            #割るたびにf倍
            z = z*f
        #fで割り切れなかったら(f+2)してf_divもリセット
        else:
            f += 2
            z = f
    
    #残ったnが以前に選んだもので割り切れないとき
    if n != 1 and all((n%i != 0 for i in A)):
        A.append(z)
        cnt += 1
    #素数のとき
    if cnt == 0:
        cnt = 1
    return cnt
if N == 1:
    ans = 0
else:
    ans = Prime_factorize(N)
print(ans)

### FIXED CODE ###

N = int(input())

def Prime_Factorize(n):
    primes = []
    while n%2 == 0:
        n//=2
        primes.append(2)
    f = 3
    while f*f <= n:
        if n%f == 0:
            n//=f
            primes.append(f)
        else:
            f += 2
    if n != 1:
        primes.append(n)
    return primes

Primes = Prime_Factorize(N)
cnt = 0
for p in Primes:
    e = 1
    z = p
    while (N%z == 0) and (N >= z):
        N //= z
        e += 1 
        z = p**e
        cnt += 1
    while N%p == 0:
        N //= p
print(cnt)
### BUGGY CODE ###

mod = 10 ** 9 + 7


def mod_pow(m, p):
    if p == 1:
        return m % mod
    return (mod_pow(m, p // 2) % mod) * (mod_pow(m, p - p // 2) % mod)


n, k = map(int, input().split())
gcd_dp = [0] * (k + 1)

for i in range(k, 0, -1):
    gcd_dp[i] = mod_pow(k // i, n)
    a = 2
    while i * a <= k:
        gcd_dp[i] -= gcd_dp[i * a]
        a += 1

ret = 0
for i in range(k + 1):
    ret += (i % mod) * (gcd_dp[i] % mod)
    ret %= mod
print(ret)


### FIXED CODE ###

Mod = 10 ** 9 + 7

n, k = map(int, input().split())
gcd_dp = [0] * (k + 1)

for i in range(k, 0, -1):
    gcd_dp[i] = pow(k // i, n, Mod)
    a = 2
    while i * a <= k:
        gcd_dp[i] -= gcd_dp[i * a]
        a += 1

ret = 0
for i in range(k + 1):
    ret += (i % Mod) * (gcd_dp[i] % Mod)
    ret %= Mod
print(ret)
### BUGGY CODE ###

import numpy as np

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

np_A = np.array(A)
for m in range(M):
    tmp = np_A.argmax()
    np_A[tmp] = np_A[tmp] / 2

print(sum(np_A))

### FIXED CODE ###

import time
import sys
import heapq

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
start = time.time()
ans = []
for a in A:
    heapq.heappush(ans, -a)

for _ in range(M):
    l = heapq.heappop(ans)
    heapq.heappush(ans, -((-l)//2) )

print(-sum(ans))
### BUGGY CODE ###

h, n = map(int, input().split())
magic = [0]*(h+1)
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h+1):
        if (magic[j] or j == 0):
            if j == h:
                continue
            key = min([j+a, h])
            if magic[key] == 0:
                magic[key] = magic[j] + b
            else:
                magic[key] = min([magic[key], magic[j]+b])
print(magic[h])

### FIXED CODE ###

h, n = map(int, input().split())
magic = [0]*(h+1)
for i in range(n):
    a, b = map(int, input().split())
    for j in range(h+1):
        if (magic[j] or j == 0):
            if j == h:
                continue
            key = min([j+a, h])
            if magic[key] == 0:
                magic[key] = magic[j] + b
            else:
                magic[key] = min([magic[key], magic[j]+b])
print(magic[h])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

a = sorted(a)

ps = [a[0]]
dup = []
for ai in a[1:]:
    is_divided = False
    for p in ps:
        if ai % p == 0:
            if ai == p and ai not in dup:
                dup.append(ai)
            is_divided = True
            break

    if not is_divided:
        ps.append(ai)

print(len(ps) - len(dup))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

a = sorted(a)

dp  = [0] * (a[-1]+1)

for ai in a:
    if dp[ai]:
        dp[ai] += 1
        continue

    i = 1
    while True:
        if ai*i >= len(dp):
            break
        dp[ai*i] += 1
        i += 1

ans = 0
for ai in a:
    if dp[ai] == 1:
        ans += 1

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

import copy
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    m = 1000
    dp = [[False]*(m+1) for _ in range(w)]
    dp[0][abs(a[0][0] - b[0][0])] = True
    for i in range(1, w):
        x = abs(a[0][i] - b[0][i])
        for j in range(m+1):
            if dp[i-1][j]:
                if j+x <= m:
                    dp[i][j+x] = True
                dp[i][abs(j-x)] = True
    for i in range(1, h):
        for j in range(w):
            buf = [False]*(m+1)
            x = abs(a[i][j] - b[i][j])
            for k in range(m+1):
                f = False
                if j == 0:
                    if dp[0][k]:
                        f = True
                else:
                    if dp[j-1][k] or dp[j][k]:
                        f = True
                if f:
                    if k+x <= m:
                        buf[k+x] = True
                    buf[abs(k-x)] = True
            dp[j] = copy.deepcopy(buf)
    for i in range(m+1):
        if dp[w-1][i]:
            print(i)
            break

if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[{0}for _ in range(w)]
dp[0]={a[0][0]-b[0][0],b[0][0]-a[0][0]}
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x,y=x-y,y-x
    t=set()
    add=t.add
    if i:
      for v in dp[j]:
        add(v+x)
        add(v+y)
    if j:
      for v in dp[j-1]:
        add(v+x)
        add(v+y)
    if i+j:dp[j]=t
print(min(map(abs,dp[w-1])))

### FIXED CODE ###

e=enumerate
h,w=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(h)]
b=[list(map(int,input().split()))for _ in range(h)]
dp=[0]*w
c=13000
for i,(a,b)in e(zip(a,b)):
  for j,(x,y)in e(zip(a,b)):
    x=abs(x-y)
    if i==j==0:
      dp[j]=2**c<<x
      continue
    t=0
    if j:
      t|=dp[j-1]<<x
      t|=dp[j-1]>>x
    if i:
      t|=dp[j]<<x
      t|=dp[j]>>x
    dp[j]=t
*a,=map(int,(bin(dp[w-1])[2:]).zfill(26001))
print(min([i for i,f in e(a[13000:])if f]+[i for i,f in e(a[13000::-1])if f]))