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

import numpy as np
n,k = map(int,input().split())
ls = np.array(list(map(int,input().split())))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
for i in range(2,n):
    st = max(0,i-k)
    dp[i] = np.min(dp[st:i]+abs(ls[i]-ls[st:i]))
print(int(dp[n-1]))

### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])
### BUGGY CODE ###

import copy
 
n, t = map(int, input().split())
L = [int(i) for i in input().split()]
LL = copy.deepcopy(L)
LL.sort()

minvalue = L[0]
maxvalue = LL[-1]
subt = 0
count = 1
flag = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  if maxvalue == L[i]:
    LL.remove(maxvalue)
    maxvalue = LL[-1]
  else:
    LL.remove(L[i])
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
#  print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
 
print(count)

### FIXED CODE ###

import copy
 
n, t = map(int, input().split())
L = [int(i) for i in input().split()]

LL = [[0] for i in range(n)]
tmax = L[-1]
for i in range(n):
  if tmax <= L[-i-1]:
    tmax = L[-i-1]
  LL[-i-1] = tmax
 
minvalue = L[0]
maxvalue = LL[0]
subt = 0
count = 1
flag = 0
flagg = 0
j = 0
for i in range(n-1):
  if minvalue > L[i]:
    minvalue = L[i]
    flag = 1
  
  maxvalue = LL[i]
 
  #if maxvalue == L[i]:
    #LL = LL[i-j+1:]
    #maxvalue = max(LL)
    #j = i+1
 
  tsubt = maxvalue - minvalue
  if tsubt > subt:
    subt = tsubt
    count = 1
  elif tsubt == subt and flag == 1:
    count += 1
  flag = 0
  #print("L[i]:{0}, min:{1}, max:{2}, subt:{3}, count:{4}".format(L[i], minvalue, maxvalue, subt, count))
 
print(count)
### BUGGY CODE ###

n,m=map(int,input().split())
if n==m//2:
  print(m//2)
  exit()
if n>m//2:
  print(m//2)
  exit()
while n<m//2:
  n+=1
  m-=2
print(m//2)


### FIXED CODE ###

n,m=map(int,input().split())
if n==m//2:
  print(m//2)
  exit()
if n>m//2:
  print(m//2)
  exit()
ans=0
ans+=n
m-=2*n
ans+=m//4
print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    while (que):
        if count > 0:
            que_warp.append(que[0])
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)

print (res_S[Dh-1][Dw-1])

### FIXED CODE ###

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    l = len(que)
    while (que):
        if l > 0:
            que_warp.append(que[0])
            l -= 1
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[Dh-1][Dw-1])
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    A = tuple(map(int, input().split()))
    l = [0] * N
    a = 0
    for j in range(N):
        x = A[j] % K
        if x == 1:
            a += 1
        l[j] = x
    for i in range(1, N):
        t = i + 1
        y = (l[0] + A[i]) % K
        if y == t:
            a += 1
        l[0] = y
        for j in range(1, N-i):
            y = (l[j-1] + A[i+j] - A[j-1]) % K
            if y == t:
                a +=1
            l[j] = y
    return a
print(main())


### FIXED CODE ###

def main():
    N, K = map(int,input().split())
    A = list(map(int, input().split()))
    s = 0
    d = {}
    d[0] = {0}
    r = 0
    l = [0] * (N + 1)
    for i, v in enumerate(A, start=1):
        if i - K >= 0:
           x = l[i - K]
           d[x].remove(i-K)
        s += v % K
        s %= K
        t = (s - i) % K
        l[i] = t
        if t in d:
            r += len(d[t])
            d[t].add(i)
        else:
            d[t] = {i}
    return r
print(main())
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import itertools
import math

def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())

    for m in range(1, n+1):

        max_n = math.sqrt(n)
        max_n = math.ceil(max_n)
        p = itertools.combinations_with_replacement(range(1,max_n+1), 3)

        ans_cnt = 0
        for v in p:
            #print(v)
            x, y, z = v
            max_value = max(x, y, z)
            min_value = min(x, y, z)
            if min_value*min_value >= m:
                break
            if max_value*max_value >= m:
                continue

            ans = x*x + y*y + z*z + x*y + y*z + z*x

            if ans == m:
                if x == y == z:
                    ans_cnt += 1
                elif x == y or y == z or x == z:
                    ans_cnt += 3
                else:
                    ans_cnt += 6

        print(ans_cnt)



if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import itertools
import math

def input():
    return sys.stdin.readline()


def resolve():
    n = int(input().rstrip())
    max_n = n
    max_n = math.sqrt(max_n)
    max_n = math.ceil(max_n)

    ans = [0] * 10050

    for i in range(1, max_n+1):
        for j in range(1, max_n+1):
            for k in range(1, max_n+1):
                v = i*i + j*j + k*k + i*j + j*k + k*i
                if v < 10050:
                    ans[v] += 1

    for i in range(n):
        print(ans[i+1])

    """
    p = itertools.combinations_with_replacement(range(1, max_n), 3)

    #print(len(list(p)))
    ans_list = []


    for v in p:

        x, y, z = v
        ans_cnt = 0
        ans_list.append(x * x + y * y + z * z + x * y + y * z + z * x)



        if ans == m:
            if x == y == z:
                ans_cnt += 1
            elif x == y or y == z or x == z:
                ans_cnt += 3
            else:
                ans_cnt += 6
    """


    """
    for m in range(1, n+1):

        max_n = math.sqrt(m)
        max_n = math.ceil(max_n)
        p = itertools.combinations_with_replacement(range(1,max_n), 3)

        ans_cnt = 0
        for v in p:
            #print(v)
            x, y, z = v
            ans = x*x + y*y + z*z + x*y + y*z + z*x

            if ans == m:
                if x == y == z:
                    ans_cnt += 1
                elif x == y or y == z or x == z:
                    ans_cnt += 3
                else:
                    ans_cnt += 6

        print(ans_cnt)
    """


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

K = int(input())
S = input()
sum = 0
for i in range(K-2):
  for j in range(i+1, K-1):
    for k in range(j+1, K):
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i] and j - i != k - j:
        sum += 1
print(sum)

### FIXED CODE ###

N = int(input())
S = input()
sum = 0
for i in range(N):
  if S[i] == "R":
    sum += S[i+1:].count("G")*S[i+1:].count("B")
  elif S[i] == "G":
    sum += S[i+1:].count("R")*S[i+1:].count("B")
  elif S[i] == "B":
    sum += S[i+1:].count("G")*S[i+1:].count("R")
for a in range(N):
  for b in range(a+1, N):
    if S[a] == S[b] or 2*b-a >= N:
      pass
    elif S[b] != S[2*b-a] and S[2*b-a] != S[a]:
      sum -= 1
print(sum)
### BUGGY CODE ###

n,q=map(int,input().split())
s=str(input())
l=[]
r=[]
for i in range(q):
    a,b=map(int,input().split())
    l.append(a)#文字列の最初
    r.append(b)#文字列の最後

for i in range(q):
    d=s[l[i]-1:r[i]]
    print(d.count("AC"))

#print(s[2:7])=ACTAC

### FIXED CODE ###

n,q=map(int,input().split())
s=str(input())
l=[]
r=[]
for i in range(q):
    a,b=map(int,input().split())
    l.append(a)#文字列の最初
    r.append(b)#文字列の最後

ans=[]
ans.append(0)
count=0
for i in range(n-1):
    if s[i:i+2]=="AC":
        count+=1
        ans.append(count)
    else:
        ans.append(count)

for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])


#print(s[2:7])=ACTAC
### BUGGY CODE ###


def main():
    n,k = map(int,input().split())
    h = list(map(int, input().split()))

    # 無限大の値
    INF = 10**10

    # DP テーブル
    # DP テーブル全体を初期化 (最小化問題なので INF に初期化)
    dp = [INF] * n

    # 初期条件
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    # ループ
    for i in range(2,n):
        # ...
        for j in range(1,min(k,i)+1):
            hk = dp[i-j] + abs(h[i-j] - h[i])
            dp[i] = min(hk,dp[i])

    # 解を得て出力
    print(dp[n-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int, input().split()))

# 無限大の値
INF = 10**10

# DP テーブル
# DP テーブル全体を初期化 (最小化問題なので INF に初期化)
dp = [INF] * n

# 初期条件
dp[0] = 0
dp[1] = abs(h[0] - h[1])

# ループ
for i in range(2,n):
    # ...
    for j in range(1,min(k,i)+1):
        hk = dp[i-j] + abs(h[i-j] - h[i])
        dp[i] = min(hk,dp[i])
    
# 解を得て出力
print(dp[n-1])
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(len(l) - 2):
    for j in range(i + 1, len(l) - 1):
        low = j + 1
        high = len(l)
        while low < high:
            mid = (low + high) // 2
            if l[mid] == l[i] + l[j]:
                low = mid
                break
            elif l[mid] < l[i] + l[j]:
                low = mid + 1
            else:
                high = mid
        ans += low - 1 - j
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(len(l) - 2):
    for j in range(i + 1, len(l) - 1):
        ans += bisect.bisect_left(l, l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

x=int(input())
for i in range(1,int(x**(1/2))+1):
    if x%i:continue

    ar,s=i,x//i
    pre=[]
    if pow(ar,5,5)==x%5:pre.append(ar)
    if  pow(s,5,5)==x%5:pre.append(s)

    for a in pre:
        d=(x-a**5)//5//a
        if d==0:print(a,0);exit()
        for b in range(1,int(abs(d)**(1/2))+1):
            if d%b:continue
            if a**3+2*b*a**2+2*b**2*a+b**3==d//b:
                print(a+b,b);exit()
            if a**3-2*b*a**2+2*b**2*a-b**3==-(d//b):print(a-b,-b);exit()


### FIXED CODE ###

x=int(input())
for i in range(-120,121):
  for j in range(-120,121):
    if pow(i,5)-pow(j,5)==x:
      print(i,j);exit()
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    for j in range(i):
        if P[j] < P[i]:
            break
    else:
        ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
v = P[0]
for i in P:
    if i <= v:
        ans += 1
        v = i
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))

p_total = 0
ans = 0

for i in range(n - k +1):
    tmp = sum(p[i:i+k])
    p_total = max(p_total, tmp)

ans = (k + p_total)/2
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))

sum_p =[0]
tmp = 0
for i in p:
    tmp += i
    sum_p.append(tmp)

max_expect = 0
for i in range(k, n+1):
    tmp = sum_p[i] - sum_p[i - k]
    max_expect = max(tmp, max_expect)

ans = (k + max_expect)/2
print(ans)
### BUGGY CODE ###

from collections import deque
N,M=map(int,input().split())

sa=deque([])
en=deque([])
for _ in range(M):
    a,b=map(int,input().split())
    if a==1:
        sa.append(b)
    elif b==N:
        en.append(a)
print('POSSIBLE' if any([x in en for x in sa]) else 'IMPOSSIBLE')

### FIXED CODE ###

N,M=map(int,input().split())
AB=[[int(x) for x in input().split()] for _ in range(M)]
sa=set()
en=set()
for a,b in AB:
    if a>b:
        a,b=b,a
    if a==1:
        sa.add(b)
    if b==N:
        en.add(a)
print('POSSIBLE' if sa&en else 'IMPOSSIBLE')
### BUGGY CODE ###

#p = lambda  x: x #print(x)

PO = "POSSIBLE"
IM = "IMPOSSIBLE"
ans = ""

# def fnc(a, ans):
# 	for i in range(N-1):
# 		if ans != "": break
# 		x = a[N-1-i]
# 		for j in range(N-1):
# 			y = a[j]
# 			if x-y == K:
# 				ans = PO
# 				break
# 			elif x-y < 0:
# 				break
# 			else:
# 				if (x-y) not in a:
# 					a.insert(0,x-y)
# 					print(a)
# 	else:
# 		ans = IM
	

N, K = map(int, input().split())		# 5 7
a = [int(i) for i in input().split()]	# 1 2 3 4 5 ...
a.sort()
#p(a)

if max(a)<K:
	ans = IM

if K in a:
	ans = PO

if ans == "":
	for i in range(N-2):
		x = a[i]
		#p(x)
		for j in range(i+1, N-1):
			y = a[j]
			#p(y)
			b = y%x
			#p(b)
			if b!=0 and K%b == 0:
				ans = PO
				#p("A")
				break

		if ans != "": break
	else:
		ans = IM
		#p("B")


print(ans)


### FIXED CODE ###

import sys
from fractions import gcd

PO = "POSSIBLE"
IM = "IMPOSSIBLE"
ans = ""


N, K = map(int, input().split())		# 5 7
a = sorted(list(map(int, input().split())))	# 1 2 3 4 5 ...

if max(a)<K:
	print(IM)
	sys.exit()

if K in a:
	print(PO)
	sys.exit()

g=a[0]
for i in range(1,N):
	g = gcd(g,a[i])

if K%g==0:
	ans=PO
else:
	ans=IM


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

n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
ans=0
for a in range(0,k):
     for b in range(0,k):
         i=0
         total=0
         while i<n:
           m=(((int(l[i][0])-a)//k)%2)+(((int(l[i][1])-b)//k)%2)
           if (m%2==0 and str(l[i][2])=="W") or (m%2==1 and str(l[i][2])=="B"):
               total=total+1
               i=i+1
           else:
               i=i+1

         else:
              ans=max(ans,total,n-total)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

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

def main():  
  import sys
  input = sys.stdin.readline
  n = int(input())
  s = input()
  def multi_index(l,x):
    return tuple([i for i,_x in enumerate(l) if _x == x])

  ans = 0
  for i in range(10):
    e = 0
    if str(i) in s:
      c = multi_index(s,str(i))[0]
      for j in range(10):
        if str(j) in s and i!=j and c<=len(s)-2:
          for q in range(c+1,len(s)-1):
            if str(j) == s[q]:
              d = q
              break
          else:
            d = -1
        elif str(j) in s and i==j and len(multi_index(s,str(i)))>=2:
          d = multi_index(s,str(i))[1]
        else:
          d = -1
        if d > c:
          for l in range(10):
            if str(l) in s and i!=j and j!=l and i!=l:
              e = multi_index(s,str(l))[-1]
              if e > d:
                ans += 1
            if str(l) in s and i!=j and j==l:
              e = multi_index(s,str(l))[-1]
              if e > d:
                ans += 1
            if str(l) in s and i==j and j!=l:
              e = multi_index(s,str(l))[-1]
              if e > d:
                ans += 1
            if str(l) in s and i==j and j==l:
              e = multi_index(s,str(l))[-1]
              if e > d:
                ans += 1
            if str(l) in s and i==l and j!=l:
              e = multi_index(s,str(l))[-1]
              if e > d:
                ans += 1
  print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = input()
def multi_index(l,x):
  return tuple([i for i,_x in enumerate(l) if _x == x])

ans = 0
for i in range(10):
  e = 0
  if str(i) in s:
    c = multi_index(s,str(i))[0]
    for j in range(10):
      if str(j) in s and i!=j and c<=len(s)-2:
        for q in range(c+1,len(s)-1):
          if str(j) == s[q]:
            d = q
            break
        else:
          d = -1
      elif str(j) in s and i==j and len(multi_index(s,str(i)))>=2:
        d = multi_index(s,str(i))[1]
      else:
        d = -1
      if d > c:
        for l in range(10):
          if str(l) in s and i!=j and j!=l and i!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i!=j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==j and j==l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
          if str(l) in s and i==l and j!=l:
            e = multi_index(s,str(l))[-1]
            if e > d:
              ans += 1
print(ans)
### BUGGY CODE ###

from fractions import gcd
 
k=int(input())
 
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1, k+1):
      ans+=gcd(gcd(i,j),l)
 
print(ans)

### FIXED CODE ###

from math import gcd
 
k=int(input())
 
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1, k+1):
      ans+=gcd(gcd(i,j),l)
 
print(ans)
### BUGGY CODE ###

# coding: utf-8
s = list(input())
q = int(input())

first = []
end = []
f = 0
for _ in range(q):
    li = list(input().split())
    if len(li) == 1:
        f = ~f
    else:
        if li[1] == '1':
            if f == 0:
                first = [li[2]] + first
            else:
                end += [li[2]]
        else:
            if f == 0:
                end += [li[2]]
            else:
                first = [li[2]] + first
s = first + s + end
if f == -1:
    s = s[::-1]
    
print(''.join(s))

### FIXED CODE ###

# coding: utf-8
s = list(input())
q = int(input())

first = []
end = []
f = 0
for _ in range(q):
    li = list(input().split())
    if len(li) == 1:
        f = ~f
    else:
        if li[1] == '1':
            if f == 0:
                first.append(li[2])
            else:
                end.append(li[2])
        else:
            if f == 0:
                end.append(li[2])
            else:
                first.append(li[2])
s = first[::-1] + s + end
if f == -1:
    s = s[::-1]
    
print(''.join(s))
### BUGGY CODE ###

import bisect
import collections
H, W = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
B = [list(map(int, input().split())) for i in range(H)]

q = collections.deque()

C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 0
for i in range(H):
    for j in range(W):
        M = max(C[i][j], M)

dp = [[[False]*((M*H*W) + 1) for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                dp[i][j][C[i][j]] = True
            else:
                for m in range(M+1):
                    if dp[i][j-1][m]:
                        dp[i][j][abs(m - C[i][j])] = True
                        dp[i][j][m+C[i][j]] = True

        else:
            if j != 0:
                for m in range(M+1):
                    if dp[i][j-1][m]:
                        dp[i][j][abs(m - C[i][j])] = True
                        dp[i][j][m+C[i][j]] = True

            for m in range(M+1):
                if dp[i-1][j][m]:
                    dp[i][j][abs(m - C[i][j])] = True
                    dp[i][j][m+C[i][j]] = True
for i in range((M*H*W)+1):
    if dp[H-1][W-1][i]:
        print(i)
        break


### FIXED CODE ###


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

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

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

for i in range(H):
    for j in range(W):
        if i == 0:
            if j == 0:
                dp[i][j] = (1 << M) << C[i][j]
            else:
                dp[i][j] |= dp[i][j-1] >> C[i][j]
                dp[i][j] |= dp[i][j-1] << C[i][j]

        else:
            if j != 0:
                dp[i][j] |= dp[i][j-1] >> C[i][j]
                dp[i][j] |= dp[i][j-1] << C[i][j]

            dp[i][j] |= dp[i-1][j] >> C[i][j]
            dp[i][j] |= dp[i-1][j] << C[i][j]

dp = bin(dp[i][j])[2:]
dp = dp[::-1]
ans = M
for i, x in enumerate(dp):
    if x == "1":
        ans = min(ans, abs(i - M))

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

a,b=map(int,input().split())
a=input()
e=""
for i in range(b):
    c,d=map(int, input().split())
    e=e+str(a[c-1:d].count("AC"))+"\n"
print(e)

### FIXED CODE ###

a,b=map(int,input().split())
a=input()
c=[0]*len(a)
for i in range(len(a)-1):
    if (a[i]+a[i+1])=="AC":c[i+1]=c[i]+1
    else:c[i+1]=c[i]
for i in range(b):
    d,e=map(int,input().split())
    print(c[e-1]-c[d-1])