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

import collections
import itertools
N = int(input())
#cnt[UDLR][x y x+y x-y][value]=set()
cnt = [[collections.defaultdict(set) for _ in range(4)] for _ in range(4)]
for _ in range(N):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    p = y + x
    q = y - x
    i = 'UDLR'.index(u)
    cnt[i][0][x].add(y)
    cnt[i][1][y].add(x)
    cnt[i][2][p].add(q)
    cnt[i][3][q].add(p)

INF = float('inf')


def calc(up, down):
    cand = up.keys() & down.keys()
    ans = min(
        [INF] +
        [v2 - v1 for c in cand for v1 in up[c] for v2 in down[c] if v2 >= v1])
    return ans


#U(0)とD(1)がx(0)が一緒:d-u(>=0)の最小値
#R(3)とL(2)がy(1)が一緒:l-r(>=0)の最小値
#U(0)とR(3)がx+y(2)が一緒:(y-x)のr-u(>=0)の最小値
#L(2)とD(1)がx+y(2)が一緒:(y-x)のd-l(>=0)の最小値
#U(0)とL(2)がy-x(3)が一緒:(y+x)のl-u(>=0)の最小値
#R(3)とD(1)がy-x(3)が一緒:(y+x)のd-r(>=0)の最小値
ans = min(
    calc(cnt[0][0], cnt[1][0]), calc(cnt[3][1], cnt[2][1]),
    calc(cnt[0][2], cnt[3][2]), calc(cnt[2][2], cnt[1][2]),
    calc(cnt[0][3], cnt[2][3]), calc(cnt[3][3], cnt[1][3]))

print('SAFE' if ans == INF else ans * 5)


### FIXED CODE ###

import collections
import itertools
N = int(input())
#cnt[URLD][x y y+x y-x][value]=set()
cnt = [[collections.defaultdict(set) for _ in range(4)] for _ in range(4)]
for _ in range(N):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    p = y + x
    q = y - x
    i = 'URLD'.index(u)
    cnt[i][0][x].add(y)
    cnt[i][1][y].add(x)
    cnt[i][2][p].add(q)
    cnt[i][3][q].add(p)

INF = float('inf')


def calc(up, down):
    ret = [INF]
    for c in up.keys() & down.keys():
        ua = sorted(up[c])
        da = sorted(down[c])
        i = j = 0
        for i in range(len(ua)):
            for j in range(j, len(da)):
                if ua[i] < da[j]:
                    ret += [da[j] - ua[i]]
                    break
            i += 1
    return min(ret)


#U(0)とD(3)がx(0)が一緒:d-u(>=0)の最小値
#R(1)とL(2)がy(1)が一緒:l-r(>=0)の最小値
#U(0)とR(1)がx+y(2)が一緒:(y-x)のr-u(>=0)の最小値
#L(2)とD(3)がx+y(2)が一緒:(y-x)のd-l(>=0)の最小値
#U(0)とL(2)がy-x(3)が一緒:(y+x)のl-u(>=0)の最小値
#R(1)とD(3)がy-x(3)が一緒:(y+x)のd-r(>=0)の最小値
ans = min(
    calc(cnt[0][0], cnt[3][0]), calc(cnt[1][1], cnt[2][1]),
    calc(cnt[0][2], cnt[1][2]), calc(cnt[2][2], cnt[3][2]),
    calc(cnt[0][3], cnt[2][3]), calc(cnt[1][3], cnt[3][3]))
print('SAFE' if ans == INF else ans * 5)
### BUGGY CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

sub = -1000000000
for i in range(len(a)):
    for j in range(len(b)):
        if j >= i:
            if sub <= b[j]-a[i]:
                sub = b[j]-a[i]
print(sub)




### FIXED CODE ###

import sys

a = []
b = []
for line in sys.stdin:
    a.append(int(line))
    b.append(int(line))

del a[0]
del a[len(a)-1]
del b[0]
del b[0]

maxv = -1000000000
minv = a[0]
for i in range(len(a)):
    maxv = max(maxv,b[i]-minv)
    minv = min(minv,b[i])
print(maxv)
### BUGGY CODE ###

import math
K=int(input())
ans=0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=math.gcd(i,math.gcd(j,k))
print(ans)

### FIXED CODE ###

import math
K=int(input())
ans=0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=math.gcd(i,math.gcd(j,k))
print(ans)
### BUGGY CODE ###

#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

def main():
    *s,=map(len,input().split("T"))
    x,y=map(int,input().split())
    start=s[0]
    n=s[2::2]
    m=s[1::2]
#    print(n,m)
#    print(start)
    dx=deque()
    dy=deque()
    dx.append(start)
    dy.append(0)
    for i in range(len(n)):
        tmp=deque()
        for j in deepcopy(dx):
            tmp.appendleft(j+n[i])
            tmp.appendleft(j-n[i])
        dx=tmp
#    print(dx)
    for i in range(len(m)):
        tmp=deque()
        for j in deepcopy(dy):
            tmp.appendleft(j+m[i])
            tmp.appendleft(j-m[i])
        dy=tmp
#    print(dy)
    if x in dx and y in dy:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

### FIXED CODE ###

#from numpy import*
#from scipy import*
from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**6)

def main():
    *s,=map(len,input().split("T"))
    x,y=map(int,input().split())
    start=s[0]
    n=s[2::2]
    m=s[1::2]
#    print(n,m)
    dx={start}
    dy={0}
#    print(dx)
    for i in n:
        dx={r+j for j in dx for r in{-i,i}}
#        print(dx)
    for i in m:
        dy={r+j for j in dy for r in{-i,i}}
#        print(dy)
    if x in dx and y in dy:
        print("Yes")
    else:
        print("No")


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

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

sa=[]
en=[]
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 ###

import math


def nc2(n):
    if n <= 1:
        return 0
    return math.factorial(n)//(2*math.factorial(n-2))

n = int(input())
a = list(map(int, input().split()))
cnt = {}
for v in a:
    if v not in cnt:
        cnt[v] = 0
    cnt[v] += 1
ans = {}
for key1 in cnt.keys():
    ans[key1] = sum(nc2(value) if key1 != key2 else nc2(value-1) for key2, value in cnt.items())
for v in a:
    print(ans[v])


### FIXED CODE ###

import math
import collections


def nc2(n):
    if n <= 1:
        return 0
    return math.factorial(n)//(2*math.factorial(n-2))


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

cnt = collections.Counter(a)
each_ans = {}
for key, value in cnt.items():
    t = nc2(value)
    each_ans[key] = (t, t-value+1)
all_sum = sum(value[0] for _, value in each_ans.items())
ans = {}
for key in cnt.keys():
    ans[key] = all_sum - each_ans[key][0] + each_ans[key][1]
for i in a:
    print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

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

stack = [0]
depth = [-1]*n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

d_to_i = [[] for _ in range(n)]

for i in range(n):
    d_to_i[depth[i]].append(i)

data = [[] for _ in range(n)]

for d in range(n-1,-1,-1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n-1-sum(data[v]))
        else:
            data[v].append(n-1)

ans = 0
two = [1]
for i in range(n):
    two.append(two[-1]*2%mod)
for i in range(n):
    now = two[n-1]-1
    for x in data[i]:
        now -= two[x]-1
        now %= mod
    ans += now

#print(ans)

x = two[n]
x = pow(x,mod-2,mod)
print(ans*x%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

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

stack = [0]
depth = [-1]*n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

d_to_i = [[] for _ in range(n)]

for i in range(n):
    d_to_i[depth[i]].append(i)

data = [[] for _ in range(n)]

for d in range(n-1,-1,-1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n-1-sum(data[v]))
        else:
            data[v].append(n-1)

ans = 0
two = [1]
for i in range(n):
    two.append(two[-1]*2%mod)
for i in range(n):
    now = two[n-1]-1
    for x in data[i]:
        now -= two[x]-1
        now %= mod
    ans += now

#print(ans)

x = two[n]
x = pow(x,mod-2,mod)
print(ans*x%mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
b=list(map(int,input().split()))
b.sort()
c=list(map(int,input().split()))
c.sort()
ans=0
import bisect
for aa in a:
  bs=bisect.bisect(b,aa)
  if bs==n:
    break
  for bb in b[bs:]:
    cs=bisect.bisect(c,bb)
    if cs==n:
      break
    ans+=len(c[cs:])
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
b=list(map(int,input().split()))
b.sort()
c=list(map(int,input().split()))
c.sort()
ans=0
import bisect
for i in range(n):
    x=bisect.bisect_left(a,b[i])
    y=bisect.bisect_right(c,b[i])
    ans+=x*(n-y)
print(ans)
### BUGGY CODE ###

N = int(input())
c = 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if (i+1)*(j+1)+(k+1)==N:
        c += 1
print(c)      

### FIXED CODE ###

N  =int(input())
c = 0
for i in range(N):
  c += (N-1)//(i+1)
print(c)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
ls = []
for j in range(n-k+1):
    x = 1
    for i in range(j,k+j):
        x *= a[i]
    ls.append(x)
for i in range(1,len(ls)):
    if ls[i] > ls[i-1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
sumf = sum(a[:k])
for i in range(1,n-k+1):
    sumn = sumf - a[i-1] + a[i+k-1]
    print("Yes" if sumn>sumf else "No")
    sumf = sumn
### BUGGY CODE ###

import numpy as np
import itertools


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

vals = np.empty((0, 4), int)
for i in range(Q):
    vals = np.append(vals, np.array([list(map(int, input().split(" ")))]), axis=0)
vals = vals[np.argsort(vals[:, 3])[::-1]]
    
maxv = 0
cand = list(itertools.combinations_with_replacement(range(1, M+1), N))
for c in cand:
    sumv = 0
    for i, v in enumerate(vals):
        
        if (maxv - sumv) > sum(vals[i:, 3]):
            break
        
        if (c[v[1]-1] - c[v[0]-1]) == v[2]:
            sumv += v[3]
    if maxv < sumv:
        maxv = sumv
print(maxv)

### FIXED CODE ###

import numpy as np
import itertools


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

vals = []
for i in range(Q):
    vals.append(list(map(int, input().split(" "))))
    
maxv = 0
cand = list(itertools.combinations_with_replacement(range(1, M+1), N))
for c in cand:
    sumv = 0
    for v in vals:
        if (c[v[1]-1] - c[v[0]-1]) == v[2]:
            sumv += v[3]
    if maxv < sumv:
        maxv = sumv
print(maxv)
### BUGGY CODE ###

n,m = map(int,input().split())
cnt = 0

while n > 0 and m > 1:
#  print(n,m)
  n -= 1
  m -= 2
  cnt += 1

cnt += m//4

print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
cnt = 0

if 2 * n >= m:
  cnt += m // 2

else:
  cnt += n
  m -= 2 * n
  cnt += m//4

print(cnt)
### BUGGY CODE ###

import math
def main():
    dpt = [math.inf] * (10**3*N + 1)
    dpt[0] = 0
    for w, v in items:
        for i in range(len(dpt)-1, v-1, -1):
            dpt[i] = min(dpt[i], dpt[i-v]+w)

    for i in range(len(dpt)-1, -1, -1):
        if dpt[i] <= W:
            break
    print(i)





if __name__ == '__main__':
    N, W = map(int, input().split())
    items = [list(map(int, input().split())) for i in range(N)]
    main()

### FIXED CODE ###

import numpy as np
import numba
import math

@numba.njit
def main():
    dpt = np.array([math.inf] * (10**3*N + 1))
    dpt[0] = 0
    for i in range(N):
        for j in range(len(dpt)-1, items[i][1]-1, -1):
            dpt[j] = min(dpt[j], dpt[j-items[i][1]]+items[i][0])

    for i in range(len(dpt)-1, -1, -1):
        if dpt[i] <= W:
            break
    print(i)

if __name__ == '__main__':
    N, W = map(int, input().split())
    items = np.array([list(map(int, input().split())) for i in range(N)])
    main()
### BUGGY CODE ###

import itertools
N, K = [int(_) for _ in input().split()]
X = [0] * N
Y = [0] * N
for i in range(N):
    X[i], Y[i] = [int(_) for _ in input().split()]
ans = float('inf')
for x1, x2 in itertools.combinations(X, 2):
    if x1 > x2:
        x1, x2 = x2, x1
    for y1, y2 in itertools.combinations(Y, 2):
        if y1 > y2:
            y1, y2 = y2, y1
        k = sum([x1 <= X[i] <= x2 and y1 <= Y[i] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)

### FIXED CODE ###

import itertools
N, K = [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(N)]
X, Y = [x for x, y in XY], [y for x, y in XY]
X_s, Y_s = sorted(X), sorted(Y)
ans = float('inf')
for x1, x2 in itertools.combinations(X_s, 2):
    for y1, y2 in itertools.combinations(Y_s, 2):
        k = sum([x1 <= X[i] <= x2 and y1 <= Y[i] <= y2 for i in range(N)])
        if k >= K:
            ans = min(ans, (x2 - x1) * (y2 - y1))
print(ans)
### BUGGY CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

A,B,C,K = MI()
ans = 0
while K>0:
    if A:
        ans+= 1
        A -= 1
    elif B:
        B -= 1
    else:
        ans -= 1
        C -= 1
    K -= 1
print(ans)


### FIXED CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))

def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

A,B,C,K = MI()
ans = 0
if K<=A:
    print(K)
elif K<=A+B:
    print(A)
else:
    print(2*A+B-K)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
S = [str(input()) for _ in range(N)]

d = defaultdict(int)
for key in S:
    d[key] += 1
    
dl = sorted(d.items(), key=lambda x: x[0], reverse=False)

for i in range(len(dl)):
  if dl[i][1] == max(d.values()):
    print(dl[i][0])

### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = [str(input()) for _ in range(N)]

d = defaultdict(int)
for key in S:
    d[key] += 1
    
dl = sorted(d.items(), key=lambda x: x[0], reverse=False)
Max = max(d.values())

for i in range(len(dl)):
  if dl[i][1] == Max:
    print(dl[i][0])
### BUGGY CODE ###

def main(N, W, P):
    dp = [[0]*(W + 1) for _ in range(N)]
    for j in range(P[0][0], W+1):
        dp[0][j] = P[0][1]

    for i in range(1, N):
        for j in range(1, W + 1):
            if j - P[i][0] < 0:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                continue

            dp[i][j] = max(dp[i-1][j-P[i][0]] + P[i][1],
                        dp[i-1][j])

    print(dp[N-1][W])

if __name__ == "__main__":
    N, W = map(int, input().split()) #N個の製品、Wの制限
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, P)

### FIXED CODE ###

def main(N, W, P):
    dp = [[0]*(W + 1) for _ in range(N)]
    for j in range(P[0][0], W+1):
        dp[0][j] = P[0][1]

    for i in range(1, N):
        for j in range(1, W + 1):
            if j - P[i][0] < 0:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                continue

            dp[i][j] = max(dp[i-1][j-P[i][0]] + P[i][1],
                           dp[i-1][j])

    print(dp[N-1][W])

if __name__ == "__main__":
    N, W = map(int, input().split()) #N個の製品、Wの制限
    P = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, W, P)
### BUGGY CODE ###

n,a,b=map(int,input().split())
s=input()
passed=0
oversea=[]
yep=False
cnt=0
for i in range(n):
    if s[i]=="b":
        oversea.append(i)
for i in range(n):
    if s[i]=="c":
        print("No")
    elif s[i]=="a":
        if passed<(a+b):
            print("Yes")
            passed+=1
        else:
            print("No")
    else:
        if oversea.index(i)<b and passed<(a+b):
            print("Yes")
            passed+=1
        else:
            print("No")
    if passed>=(a+b):
        yep=True
        cnt=len(s)-(i+1)
        break
if yep:
    for i in range(cnt):
        print("No")

### FIXED CODE ###

n,a,b=map(int,input().split())
s=input()
passed=0
oversea=0
yep=False
cnt=0
for i in range(n):
    if s[i]=="c":
        print("No")
    elif s[i]=="a":
        if passed<(a+b):
            print("Yes")
            passed+=1
        else:
            print("No")
    else:
        if oversea<b and passed<(a+b):
            print("Yes")
            passed+=1
            oversea+=1
        else:
            print("No")
#     if passed>=(a+b):
#         yep=True
#         cnt=len(s)-(i+1)
#         break
# if yep:
#     for i in range(cnt):
#         print("No")
### BUGGY CODE ###

n,m = map(int,input().split())
a = [input() for i in range(n)]
b = list(zip(*a))
ans = 0
for i in range(m-1):
  b1 = b[i]
  b2 = b[i+1]
  ct1 = [[0 for k in range(n-j+1)] for j in range(n+1)]
  for j in range(n+1):
    b2c = b2[:n-j]
    for k in range(n-j):
      if b1[k+j] == b2c[k]:
        ct1[j][k+1] += ct1[j][k]+1
      else:
        ct1[j][k+1] += ct1[j][k]
  ct2 = [[0 for k in range(n-j+1)] for j in range(n+1)]
  for j in range(n+1):
    b1c = b1[:n-j]
    for k in range(n-j):
      if b2[k+j] == b1c[k]:
        ct2[j][k+1] += ct2[j][k]+1
      else:
        ct2[j][k+1] += ct2[j][k]
  dp = [[10**6 for i in range(n+1)] for j in range(n+1)]
  dp[0][0] = 0
  for i in range(n+1):
    for j in range(n+1):
      if i <= j:
        cost = ct2[j-i][n-j]
      else:
        cost = ct1[i-j][n-i]
      if i < n:
        dp[i+1][j] = min(dp[i+1][j],dp[i][j]+cost)
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cost)
  ans += dp[-1][-1]
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = [input().rstrip() for i in range(n)]
b = list(zip(*a))
for i in range(m):
  b[i] = "".join(b[i])
ans = 0
ct1 = [[0 for k in range(n-j+1)] for j in range(n+1)]
ct2 = [[0 for k in range(n-j+1)] for j in range(n+1)]
dp = [[10**5 for i in range(n+1)] for j in range(n+1)]
for i in range(m-1):
  b1 = b[i]
  b2 = b[i+1]
  for j in range(n+1):
    ct1[j][0] = 0
    ct2[j][0] = 0
    for k in range(n-j):
      ct1[j][k+1] = ct1[j][k]
      ct2[j][k+1] = ct2[j][k]
      if b1[k+j] == b2[k]:
        ct1[j][k+1] += 1
      if b2[k+j] == b1[k]:
        ct2[j][k+1] += 1
  dp[0][0] = 0
  for i in range(n+1):
    if i < n:
      dp[i+1][0] = 10**6
    for j in range(n+1):
      if i == 0 and j < n:
        dp[i][j+1] = 10**6
      if i <= j:
        cost = ct2[j-i][n-j]
      else:
        cost = ct1[i-j][n-i]
      if j < n:
        dp[i][j+1] = min(dp[i][j+1],dp[i][j]+cost)
      if i < n:
        dp[i+1][j] = dp[i][j]+cost
  ans += dp[-1][-1]
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors
    
    
kosuu = int(input())
nums = list(map(int,input().split()))

temp_arr=[]
for temp in nums:
    temp_arr.append(make_divisors(temp))
    
temp_arr2 = sum(temp_arr,[])
temp_arr2.sort(reverse=True)
for temp in temp_arr2:
    if temp_arr2.count(temp) == kosuu -1 or temp_arr2.count(temp) == kosuu:
        print(temp)
        break

### FIXED CODE ###

def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

kosuu = int(input())
nums = list(map(int,input().split()))

L = []
R = []
for temp in range(kosuu-1):
    if temp == 0:
        L.append(nums[0])
    else:
        L.append(gcd(L[temp-1],nums[temp]))

for temp in range(kosuu-1):
    if temp == 0:
        R.append(nums[kosuu-1])
    else:
        R.append(gcd(R[temp-1],nums[len(nums)-temp-1]))

saidai=[]
for i in range(kosuu):
    if i == 0:
        saidai.append(L[-1])
    elif i == kosuu-1:
        saidai.append(R[-1])
    else:
        saidai.append(gcd(L[i-1],R[-1-i]))

print(max(saidai))
### BUGGY CODE ###

n = int(input())
S = list(input().split())
q = input()
T = input().split()
 
count = 0
for key in T:
    U = S + [key]
    i = 0
    while U[i] != key:
        i = i+1
    if i != n:
        count = count + 1
print(count)

### FIXED CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
 
count = 0
for key in T:
    left = 0
    right = n
    while left < right:
        mid = (right + left) // 2
        if S[mid] == key:
            count = count + 1
            break
        if key < S[mid]:
            right = mid
        else:
            left = mid + 1
print(count)