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

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    l = []
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i- k), i))
print(dp[n - 1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    l = []
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(0, i- k), i))
print(dp[n - 1])
### BUGGY CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
b=a.copy()
ans=sum(a)
for k in range(n):
  d=0
  for i in range(n):
    b[i]=min(b[i],a[i-k])
    d+=b[i]
  ans=min(d+x*k,ans)
print(ans)

### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
b=a.copy()
ans=sum(a)
for k in range(n):
  for i in range(n):b[i]=min(b[i],a[i-k])
  ans=min(sum(b)+x*k,ans)
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
l, r = [0] * Q, [0] * Q

for i in range(Q):
    l[i], r[i] = [int(x) for x in input().split()]

for i in range(Q):
    res = 0
    for j in range(l[i] - 1, r[i] - 1):
        if S[j:j+2] == 'AC':
            res += 1
    print(res)


### FIXED CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
m = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        m[i] = m[i-1] + 1
    else:
        m[i] = m[i-1]

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

def pow_r(x, n):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2, (n - 1) // 2)

n, p = [int(i) for i in input().split()]
max_x = int(p**(1/n))
ans = 1

if n >= p:
    print(1)
else:
    for i in range(max_x+1, 1, -1):
        if p % pow_r(i,n) == 0:
            ans = i
            break
    print(ans)

### FIXED CODE ###

n, p = [int(i) for i in input().split()]
tmp = p**(1/n)
if tmp - int(tmp) > 0.999:
    max_x = int(tmp) + 1
else:
    max_x = int(tmp)
ans = 1
for i in range(max_x, 1, -1):
    if p % pow(i,n) == 0:
        ans = i
        break
print(ans)
### BUGGY CODE ###

n, capacity = map(int, input().split())
dp = [0] * (capacity + 1)
for _ in range(n):
    w, v = map(int, input().split())
    for j in range(capacity, -1, -1):
        if j - w >= 0:
            dp[j] = max(dp[j], dp[j - w] + v)
print(dp[-1])

### FIXED CODE ###

import numpy as np


n, capacity = map(int, input().split())
dp = np.zeros(capacity + 1, dtype=np.int64)
for _ in range(n):
    w, v = map(int, input().split())
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print(dp[-1])
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
if N > 5*10**4 :
    parameter = 0.9995
else :
    parameter = 0.995
ANS = [0]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
arr = [round(float(input()) * pow(10, 9)) for _ in range(n)]
arr2 = [div(x, 2) for x in arr]
arr5 = [div(x, 5) for x in arr]

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        if arr2[i] + arr2[j] >= 18 and arr5[i] + arr5[j] >= 18:
            ans += 1

print(ans)

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
cost=[[0 for _ in range(H*W)] for i in range(D)]
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
    if L1[j]%D!=0:
      cost[L1[j]%D][(L1[j]-L1[j]%D)//D]=[i,j,0]
    else:
      cost[L1[j]%D][(L1[j]-1-L1[j]%D)//D]=[i,j,0]
for i in range(D):
  for j in range(1,len(cost[i])):
    if cost[i][j]!=0:
      cost[i][j][2]=cost[i][j-1][2]+abs(cost[i][j][0]-cost[i][j-1][0])+abs(cost[i][j][1]-cost[i][j-1][1])
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  c=A%D
  a=(A-c)//D
  b=(B-c)//D
  if c==0:
    a,b=a-1,b-1
  print(cost[c][b][2]-cost[c][a][2])

### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
cost=[[0 for _ in range((H*W)//D+1)] for i in range(D)]
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
    if L1[j]%D!=0:
      cost[L1[j]%D][L1[j]//D]=[i,j,0]
    else:
      cost[L1[j]%D][(L1[j]//D)-1]=[i,j,0]
for i in range(D):
  for j in range(1,len(cost[i])):
    if cost[i][j]!=0:
      cost[i][j][2]=cost[i][j-1][2]+abs(cost[i][j][0]-cost[i][j-1][0])+abs(cost[i][j][1]-cost[i][j-1][1])
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  c=A%D
  a=A//D
  b=B//D
  if c==0:
    a,b=a-1,b-1
  print(cost[c][b][2]-cost[c][a][2])
### BUGGY CODE ###

import heapq as hp
n = int(input())
a = list(map(int, input().split()))
han = list(map(lambda x:x*(-1), a))
hp.heapify(han)
b = hp.heappop(han)*(-1)
che,re = [1 for i in range(b)],[]
for i in a:
    if i in re:
        che[i-1] = 0
    else:
        re.append(i)
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
ans = 0
for i in re:
    if che[i-1] == 1:
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = max(a)
che = [1 for i in range(b)]
for i in a:
    if che[i-1] == 1:
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
        che[i-1] = 2
    elif che[i-1] == 2:
        che[i-1] = 0
ans = 0
for i in a:
    if che[i-1] == 2:
        ans += 1
print(ans)
### BUGGY CODE ###


n = int(input())
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(n - sum(x > a[i] for x in b), n):
        ans += sum(x > b[j] for x in c)

print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))
ans = 0
def bin_search(x, n, flag):
    if flag == True:
        return bisect_left(x, n)
    else:
        return bisect_right(x, n)



for i in range(n):
    ans += bin_search(a, b[i], True) * (n - bin_search(c, b[i], False))

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

import itertools
from collections import Counter

n=list(input())

a=len(list(itertools.combinations(n,2)))

counter = Counter(n)
for w, c in counter.most_common():
  a -= len(list(itertools.combinations(w*c,2)))
print(a+1)    

### FIXED CODE ###

from collections import Counter

n=list(input())
l=len(n)
a=l*(l-1)/2

counter = Counter(n)
for w, c in counter.most_common():
  a -= c*(c-1)/2
print(int(a+1))
### BUGGY CODE ###

K=int(input());q=[(1,1)];m={}
while len(q):
 n,s=q.pop()
 if not n in m:m[n]=s;q+=[(n*10%K,s)];q=[((n+1)%K,s+1)]+q
print(m[0])

### FIXED CODE ###

from collections import deque

que = deque()

K = int(input())

que.append((1, 1))
visited = {}

while len(que) != 0:
    num, step = que.popleft()
    if num in visited:
        continue
    visited[num] = step
    que.appendleft((num * 10 % K, step))
    que.append(((num + 1) % K, step + 1))

print(visited[0])
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans = ans*i
if ans > 1e18:
    print("-1")
    sys.exit()
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
if a[0]==0:
  print("0")
else:
  ans = 1
  for i in range(n):
    ans = ans*a[i]
    if ans > 1e18:
      print("-1")
      break
  else:
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


N = int(input())
a_list = list(map(int, input().split()))
a_list_unique = list(set(a_list))
cnt = 0
a_dict = {}
for i in a_list_unique:
    a_dict[i] = a_list.count(i)
    if i <= a_dict[i]:
        cnt +=  a_dict[i] - i
    else:
        cnt += a_dict[i]
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import Counter


N = int(input())
a_list = list(map(int, input().split()))
a_list_unique = list(set(a_list))
a_cnt = Counter(a_list)
cnt = 0
for i in a_list_unique:
    a_dict = a_cnt[i]
    if i <= a_dict:
        cnt +=  a_dict - i
    else:
        cnt += a_dict
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

MAX_INT = 2**62-1
sys.setrecursionlimit(10**5)

input = sys.stdin.readline

def n_input():
    return input().split()


class ModOperation:

    def __init__(self, mod):
        self.mod = mod

    def add(self, a, b):
        return (a + b) % self.mod

    def sub(self, a, b):
        return (a - b) % self.mod

    def mul(self, a, b):
        m = self.mod
        return ((a % m) * (b % m)) % m

    def div(self, a, b):
        m = self.mod
        return self.mul(a, pow(b, m-2, m))


N = 2 * (10**5) + 1
MOD = 10**9 + 7
mod = ModOperation(MOD)

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = mod.mul(fact[i-1], i)
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre, cur] = num, ways
        return num, ways

    m = MOD
    f, fi = fact, fact_inv
    memo = {}
    write = sys.stdout.write

    for i in range(1, len(g)):
        write(str(dfs(None, i)[1]))
        write('\n')


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

    for _ in range(n-1):
        a, b = map(int, n_input())
        g[a].append(b)
        g[b].append(a)

    solve(g)


if __name__ == "__main__":

    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import reduce

MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(*args, mod=MOD):
    return reduce(lambda a, b: a * b % mod, args)


def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(dp[pre], dp[cur], fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        i = size[cur]
        temp = mul(ans[pre], f[n-i-1], fi[n-1], f[i], pow(dp[cur], m-2, m))
        ans[cur] = mul(f[n-1], temp, fi[n-i], dp[cur], fi[i-1])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
 
ans = 0
for i in range(0, N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        if L[-1] > a - b:
            ans += len(L[j+1:])
        else:
            for k in range(j+1, N):
                c = L[k]
                if c > a - b:
                    ans += 1
                else:
                    break
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()

'''
リストをソートし、a, b <= cとなるようにa, bを取り出せば、
a < b + c, b < c + a という条件は満たすので、
a, bを取り出したとき、c < a + b を満たすcを二分探索で探す
'''

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(l, l[i]+l[j]) - j - 1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    acc = [0 for j in range(n+1)]
    for j in range(n):
        acc[max(0, j - a[j])] += 1
        acc[min(n-1, j + a[j]) + 1] -= 1
    for j in range(n):
        acc[j+1] += acc[j]
    a = acc[:-1]
    if sum(a) == n * (n-1):
        break
print(" ".join(map(str, a)))


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(k):
    acc = [0 for j in range(n+1)]
    for j in range(n):
        acc[max(0, j - a[j])] += 1
        acc[min(n-1, j + a[j]) + 1] -= 1
    for j in range(n):
        acc[j+1] += acc[j]
    a = acc[:-1]
    if sum(a) == n * n:

        break
print(" ".join(map(str, a)))
### BUGGY CODE ###

def bubble_sort(ary):
    flag = True
    cnt = 0
    i = 0
    while flag:
        flag = False
        for j in range(len(ary) - 1, i, -1):
            if ary[j] < ary[j - 1]:
                ary[j], ary[j - 1] = ary[j - 1], ary[j]
                flag = True
                cnt += 1
        i += 1

    # for i in range(0, len(ary) - 1):
    #     for j in range(len(ary) - 1, i, -1):
    #         if ary[j] < ary[j - 1]:
    #             ary[j], ary[j - 1] = ary[j - 1], ary[j]
    #             cnt += 1

    return cnt


n = int(input())
ary = [int(_) for _ in input().split()]
print(bubble_sort(ary))



### FIXED CODE ###

INF = 10**10


def merge(ary, left, mid, right):
    lry = ary[left:mid]
    rry = ary[mid:right]
    lry.append(INF)
    rry.append(INF)

    cnt = 0
    i = 0
    j = 0
    for k in range(left, right):
        if lry[i] <= rry[j]:
            ary[k] = lry[i]
            i += 1
        else:
            ary[k] = rry[j]
            j += 1
            cnt += len(lry) - 1 - i

    return cnt


def merge_sort(ary, left, right):
    cnt = 0
    if left + 1 < right:
        mid = (left + right) // 2
        cnt += merge_sort(ary, left, mid)
        cnt += merge_sort(ary, mid, right)
        cnt += merge(ary, left, mid, right)

    return cnt


if __name__ == '__main__':
    n = int(input())
    ary = [int(_) for _ in input().split()]
    print(merge_sort(ary, 0, n))
### BUGGY CODE ###

def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    return(dp[l+1][0])

def y_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    seq_flag=False
    ans=0
    next_bit=0
    kuri_cal=0
    for i in range(l-1):
        num=int(rev[i])+next_bit
        next_num=int(rev[i+1])
        if not seq_flag:
            if (num<5) or (num==5 and next_num<5):
                ans+=num
                next_bit=0
                kuri_cal=0
                continue
            seq_s=i
            seq_flag=True
            kuri_cal=10-num
            next_bit+=1
            continue
        #print(kuri_cal)
        if num<5:
            ans+=(kuri_cal+num)
            kuri_cal=0
            next_bit=0
            seq_flag=False
        elif num>5:
            kuri_cal+=10-num
        else:
            if next_num<5:
                ans+=(kuri_cal+num)
                next_bit=0
                kuri_cal=0
                seq_flag=False
            else:
                kuri_cal+=10-num
    last=int(tmp[0])+next_bit
    ans+=kuri_cal+min(last,11-last)
    return ans

n=input()
ans=dp_solver(n)
print(ans)

### FIXED CODE ###

def dp_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    dp=[[float("inf") for _ in range(2)] for _ in range(l+2)]
    dp[0][0]=0
    for i in range(l+1):
        for j in range(2):
            num=int(rev[i])
            num+=j
            if num<10:
                dp[i+1][0]=min(dp[i+1][0],dp[i][j]+num)
            if num>0:
                dp[i+1][1]=min(dp[i+1][1],dp[i][j]+(10-num))

    import numpy as np
    dp=np.array(dp)
    return(dp[l+1])

def y_solver(tmp):
    l=len(tmp)
    rev=tmp[::-1]+"0"
    seq_flag=False
    ans=0
    next_bit=0
    kuri_cal=0
    for i in range(l-1):
        num=int(rev[i])+next_bit
        next_num=int(rev[i+1])
        if not seq_flag:
            if (num<5) or (num==5 and next_num<5):
                ans+=num
                next_bit=0
                kuri_cal=0
                continue
            seq_s=i
            seq_flag=True
            kuri_cal=10-num
            next_bit+=1
            continue
        #print(kuri_cal)
        if num<5:
            ans+=(kuri_cal+num)
            kuri_cal=0
            next_bit=0
            seq_flag=False
        elif num>5:
            kuri_cal+=10-num
        else:
            if next_num<5:
                ans+=(kuri_cal+num)
                next_bit=0
                kuri_cal=0
                seq_flag=False
            else:
                kuri_cal+=10-num
    last=int(tmp[0])+next_bit
    ans+=kuri_cal+min(last,11-last)
    return ans

n=input()
ans=y_solver(n)
print(ans)
### BUGGY CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _i(): return int(sys.stdin.readline().strip())
def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
m = None
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)
    if m is None or m<t: m=t

# initialize
st = ab[0][0]
m = m * (h+w-2) + st + 1
dp = [[[False] * m for _ in range(w)] for _ in range(h)]
dp[0][0][st] = True
for ij in range(1,h+w-1):
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        x = ab[i][j]
        nxt = dp[i][j]
        #
        if i==0: ref= dp[i][j-1]
        elif j==0: ref = dp[i-1][j]
        else: ref = list(map(lambda x: x[0]|x[1], zip(dp[i][j-1], dp[i-1][j])))
        #
        for i,tf in enumerate(ref):
            if not tf: continue
            nxt[abs(i-x)]= True
            nxt[i+x] = True
# stdout
ref=dp[h-1][w-1]
for k in range(m):
    if ref[k]:
        print(k)
        break


### FIXED CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)

# initialize
dp = [[None for _ in range(w)] for _ in range(h)]
dp[0][0] = {ab[0][0]}
hw1 = h + w - 1
for ij in range(1,hw1):
    iend = ( hw1 - ij ) * 80
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        ref = set()
        if i>0: ref|= dp[i-1][j]
        if j>0: ref|= dp[i][j-1]
        #
        x = ab[i][j]
        nxt = dp[i][j] = set()
        for idx in ref:
            ix = abs(idx-x)
            if ix<=iend: nxt.add(ix)
            ix = idx + x
            if ix<=iend: nxt.add(ix)
            
# stdout
print(min(dp[h-1][w-1]))
### BUGGY CODE ###

n = int(input())
s = input()

s_bin = '0b' + s.replace('.', '0').replace('#', '1')
min_cost = n

for i in range(n+1):
    cand_s_bin = '0b' + ('0' * i) + ('1' * (n-i))
    diff = bin(int(s_bin, 2) ^ int(cand_s_bin, 2))
    cost = diff.count('1')
    if cost < min_cost:
        min_cost = cost

print(min_cost)


### FIXED CODE ###

n = int(input())
s = input()

def calc():
    min_cost = n
    left_cost = 0
    right_cost = s.count('.')

    cost = left_cost + right_cost
    if cost < min_cost:
        min_cost = cost

    for i in range(n):
        if s[i] == '#':
            left_cost += 1
        else:
            right_cost -= 1
        cost = left_cost + right_cost
        if cost < min_cost:
            min_cost = cost

    return(min_cost)

print(calc())
### BUGGY CODE ###

from collections import Counter
N=int(input())
S=[Counter(input()) for n in range(N)]
c=0
for s in S:
    c+=(S.count(s)*(S.count(s)-1))//2
    S=[i for i in S if i!=s]
    if len(S)==0:
        break
print(c)

### FIXED CODE ###

N=int(input())
S=["".join(sorted(input())) for n in range(N)]
d={}
for s in S:
    if s not in d:
        d[s]=1
    else:
        d[s]+=1
c=0
for k in d:
    n=d[k]
    c+=(n*(n-1))//2
print(c)
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(k):
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1
print(a, b)

### FIXED CODE ###

a, b, k = map(int, input().split())
sub = k - a  
a = max(0, a - k)
b = max(0, min(b - sub, b))
print(a, b)
### BUGGY CODE ###

N = int(input())
C = input()
A = []
for c in C:
    if c=='W':
        A.append(0)
    else:
        A.append(1)
l = 0
r = N - 1
ans = 0
while l < r:
    if not A[l] and A[r]:
        ans+=1
        l +=1
        r-=1
    elif not A[l]:
        r-=1
    elif A[r]:
        l+=1
print(ans)

### FIXED CODE ###

N = int(input())
C = input()

r = C.count('R')
ans = C[:r].count('W')
print(ans)