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

N,M,K=map(int,input().split())
fdic={}
for i in range(1,N+1):
  fdic[i]=set()  
for i in range(M):
  a,b=map(int,input().split())
  fdic[a].add(b)
  fdic[b].add(a)

bdic={}
for i in range(1,N+1):
  bdic[i]=set()
for i in range(K):
  c,d=map(int,input().split())
  bdic[c].add(d)
  bdic[d].add(c)
  
#print(fdic)
#print(bdic)

dic_cluster={}
cluster_num=0
cluster_list=[0]*(N+1)

for i in range(1,N+1):
  if cluster_list[i]>0:
    continue
  else:
    cluster_num+=1
    dic_cluster[cluster_num]=set()
    visited=set()
    queue=[i]
    while(len(queue)>0):
      new_queue=set()
      for q in queue:
        cluster_list[q]=cluster_num
        dic_cluster[cluster_num].add(q)
        visited.add(q)
        nx=fdic[q]
        for n in nx:
          if not n in visited:
            new_queue.add(n)

      queue=new_queue
      #print(new_queue)
      
#print(cluster_list)
#print(dic_cluster)

candlist=[]
for i in range(1,N+1):
  cluster_i=set(dic_cluster[cluster_list[i]])  
  #print(cluster_i.difference(fdic[i]).difference(bdic[i]))  
  candlist.append(str(len(cluster_i.difference(bdic[i]))-len(fdic[i])-1))
  
print(" ".join(candlist))


### FIXED CODE ###

N,M,K=map(int,input().split())
fdic={}
for i in range(1,N+1):
  fdic[i]=set()  
for i in range(M):
  a,b=map(int,input().split())
  fdic[a].add(b)
  fdic[b].add(a)

blist=[]
for i in range(K):
  c,d=map(int,input().split())
  blist.append((c,d))
  
#print(fdic)
#print(blist)

dic_cluster={}
cluster_num=0
cluster_list=[0]*(N+1)

for i in range(1,N+1):
  if cluster_list[i]>0:
    continue
  else:
    cluster_num+=1
    dic_cluster[cluster_num]=set()
    visited=set()
    queue=[i]
    while(len(queue)>0):
      new_queue=set()
      for q in queue:
        cluster_list[q]=cluster_num
        dic_cluster[cluster_num].add(q)
        visited.add(q)
        nx=fdic[q]
        for n in nx:
          if not n in visited:
            new_queue.add(n)

      queue=new_queue
      #print(new_queue)
      
#print(cluster_list)
#print(dic_cluster)

candlist=[0]*(N+1)
for i in range(1,N+1):
  candlist[i]=len(dic_cluster[cluster_list[i]])-len(fdic[i])-1
for c,d in blist:
  if d in dic_cluster[cluster_list[c]]:
    candlist[c]-=1
    candlist[d]-=1
  
print(" ".join(map(str,candlist[1:])))
### BUGGY CODE ###

N = int(input())
A = input().split()
for j in range(N):
    for i in A:
        A.remove(i)
        if A.count(i) == 0:
            N -= 1
            continue
        else:
            print("NO")
            break
if N == 0:
    print("YES")


### FIXED CODE ###

N = int(input())
A = input().split()
if len(A) == len(set(A)):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N=int(input())
S=list(input())
for i in range(len(S)):
    S[i]=-1 if S[i]=="W" else 1
data=[0 for i in range(N)]

for i in range(N):
    data[i]=-1*sum([S[m] for m in range(0,i) if S[m]==-1])+sum([S[m] for m in range(i+1,N) if S[m]==1])
print(min(data))


### FIXED CODE ###

N=int(input())
S=list(input())
data=[0 for i in range(N)]
data[0]=S[1:].count("E")
for i in range(N-1):
    if S[i]=="W":
        data[i+1]+=1
    if S[i+1]=="E":
        data[i+1]-=1
    data[i+1]+=data[i]
print(min([i for i in data]))
### BUGGY CODE ###

import heapq
import math
xs, ys, xt, yt = map(int, input().split())
N = int(input())

minRadiation = {(xs, ys):0, (xt, yt):10**20}
ToVisit = {(xs, ys, 0), (xt, yt, 0)}
for _ in range(N):
    x, y, r = map(int, input().split())
    ToVisit |= {(x, y, r)}
    minRadiation[(x, y)] = 10**20

Q = [(0, xs, ys, 0)]
heapq.heapify(Q)
while Q:
    nowRadiation, nowx, nowy, nowr = heapq.heappop(Q)
    if (nowx, nowy) == (xt, yt):
        print(nowRadiation)
        break
    elif (nowx, nowy, nowr) in ToVisit:
      ToVisit ^= {(nowx, nowy, nowr)}
      for nextx, nexty, nextr in ToVisit:
          tempTime = max(0, math.sqrt((nextx-nowx)**2 + (nexty-nowy)**2) - nowr - nextr) + nowRadiation
          if minRadiation[(nextx, nexty)] > tempTime:
              minRadiation[(nextx, nexty)] = tempTime
              heapq.heappush(Q, (tempTime, nextx, nexty, nextr))

### FIXED CODE ###

import heapq
import math
xs, ys, xt, yt = map(int, input().split())
N = int(input())

Coordinate = {-1: (xs, ys, 0), N:(xt, yt, 0)}
minRadiation = {int(i):10**20 for i in range(-1, N+1)}
ToVisit = {int(i) for i in range(-1, N+1)}
for i in range(N):
    x, y, r = map(int, input().split())
    Coordinate[i] = (x, y, r)

Q = [(0, -1)]
heapq.heapify(Q)
while Q:
    nowRadiation, index = heapq.heappop(Q)
    if index == N:
        print(nowRadiation)
        break
    elif index in ToVisit:
      ToVisit.difference_update({index})
      nowx, nowy, nowr = Coordinate[index]
      for nextIndex in ToVisit:
          nextx, nexty, nextr = Coordinate[nextIndex]
          tempTime = max(0, math.sqrt((nextx-nowx)**2 + (nexty-nowy)**2) - nowr - nextr) + nowRadiation
          if minRadiation[nextIndex] > tempTime:
              minRadiation[nextIndex] = tempTime
              heapq.heappush(Q, (tempTime, nextIndex))
### BUGGY CODE ###

A = input()
a = int(A)
ans  = 0 

for i in range(len(A)):
    for j in range(i+5,len(A)+1):
        t = A[i:j]
        ans += (int(t)%2019==0)
            # print(t)
# print(ans)

L =[]
for i in range(len(A)):
    t = A[i:i+4]
    L.append(int(t)%2019)
B = 0
for i in range(len(L)):
    T = L[i]
    for j in range(i+1,len(L)-3):
        T = 10*T+int(A[3+j])
        if T%2019==0:
            B+=1
            # print('w',T)
print(B)

### FIXED CODE ###

s=list(map(int,list(input())))[::-1]

n=len(s)
D=[0]*(n+1)
c=[0]*(n+1)
ans = 0
f = 0
dp = [0]*(2020)
dp[0]+=1
tmp =0
x = 1
for e,i in enumerate(s):
    tmp = (tmp+x*i)%2019
    ans += dp[tmp]
    dp[tmp]+=1
    x = x*10 %2019
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
a=sorted(a)
i=1
while True:
    flag=True
    x=a[-1]*i
    for aa in range(n-1):
        if x%a[aa]!=0:
            flag=False
            break
    if flag==True:
        print(x)
        exit()
    i+=1

### FIXED CODE ###

import fractions
N = int(input())
T = [int(input()) for i in range(N)]
 
ans = T[0]
for i in range(N-1):
    ans = ans * T[i+1]//fractions.gcd(ans, T[i+1])
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = sorted([list(map(int, readl().rstrip().split())) for _ in range(N)],key=lambda x:x[2])
  Dn = [None for _ in range(Q+1)]
  for i in range(Q):
    Dn[i] = int(readl().rstrip())
  Dn[Q] = 10**10
  ans = []

  for s,t,x in STX:
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    si,ei=map(int,input().split())
    print(s[si-1:ei].count("AC"))

### FIXED CODE ###

from bisect import bisect_left as b_l
n,q=map(int,input().split())
s=input()
pi=0
aci=[]
while 1:
    ni=s[pi:].find("AC")
    if ni==-1:
        break
    aci+=[ni+pi]
    pi+=ni+1
for i in range(q):
    si,ei=map(int,input().split())
    print(b_l(aci,ei-1)-b_l(aci,si-1))
### BUGGY CODE ###

def uauau():
    N = int(input())
    aA=sorted(set(int(_) for _ in input().split()))
    N = len(aA)
    def ggg(i,j):
        i %= j
        if i == 0:
            return j
        else:
            return ggg(j,i)

    if len(aA) == 1:
        print(aA[0])
    else:
        iMin = aA[0]
        iMax = aA[-1]
        if iMin  == 1:
            print(1)
        else:
            iMt = max(i % iMin for i in aA)
            if iMt == 0:
                print(iMin)
                exit()
            elif iMt  == 1:
                print (1)
            else:
                iM = iMax
                for i in range(N):
                    iA = aA[i]
                    for j in range(i+1,N):
                        iMt = ggg(aA[j],iA)
                        if iMt < iM:
                            iM = iMt
                    if iM == 1:
                        print(1)
                        exit()
                print(iM)
uauau()


### FIXED CODE ###

#gcdか....
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = sorted(set(int(_) for _ in input().split()))
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
print(b)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = [int(input()) for _ in range(M)]
s = 1
s_ = 0
for n in range(1, N+1):
  if n in A:
    s, s_ = 0, s
    continue
  s, s_ = (s + s_) % (10 ** 9 + 7), s
print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
A = set([int(input()) for _ in range(M)])
s = [0 for _ in range(N + 1)]
s[0] = 1
if 1 not in A:
  s[1] = 1

for n in range(2, N+1):
  if n in A:
    continue
  else:
    s[n] = s[n-1] + s[n-2]
print(s[-1] % (10 ** 9 + 7))
### BUGGY CODE ###

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

for i in range(N):
    temp=X[:i]+X[i+1:]
    temp.sort()
    print(temp[N//2-1])

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
temp = sorted(X)
med = (temp[N//2]+temp[N//2-1])/2
for i in range(N):
    if X[i] < med:
        print(temp[N//2])
    else:
        print(temp[N//2-1])
### BUGGY CODE ###

m = list(map(int,input().split()))
a=[int(input()) for i in range(m[2])]

n=[]
for i in range(m[0]):
    n.append(m[1])

for i in range(m[2]):
    n[a[i]-1] +=1
    n = [i-1 for i in n]

for i in range(m[0]):
    if n[i]>0:
        print('Yes')
    else:
        print('No')
    

### FIXED CODE ###

m = list(map(int,input().split()))
n = [0] * m[0]

for i in range(m[2]):
    n[int(input())-1] += 1
  
for i in range(m[0]):
    if n[i] - m[2] + m[1] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()
cnt=0
for i in range(n-2):
  for j in range(i+1,n-1):
    ma=n-1
    while ma>=j+1:
      if L[ma]<L[i]+L[j]:
        cnt+=ma-j
        break
      else:
        ma-=1
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left

def main():
    n=int(input())
    l=sorted(list(map(int,input().split())))
    ans=0
    for i in range(n-2):
        a=l[i]
        for j in range(i+1,n-1):
            ans+=bisect_left(l,a+l[j])-j-1
    print(ans)

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

n = int(input())

A = []
for i in range(0, n):
    A.append(int(input()))

cnt = 0
def insertion_sort(L, n, g):
    global cnt
    for i in range(g, n):
        v = L[i]
        j = i - g
        while 0 <= j and v < L[j]:
            L[j+g] = L[j]
            j -= g
            cnt += 1
        L[j+g] = v


def shell_sort(L, n):
    global G
    for i in G:
        insertion_sort(L, n, i)

g = []
for i in range(0, 100, 2):
    x = pow(2, i)
    if n < x:
        break
    else:
        g.append(x)

G = list(reversed(g))
B = A[:]
shell_sort(B, n)

print(len(G))
print(' '.join(str(x) for x in G))
print(cnt)
for i in B:
    print(i)

### FIXED CODE ###

import sys
n = int(input())
A = list(map(int, sys.stdin))

cnt = 0
def insertion_sort(L, n, g):
    global cnt
    for i in range(g, n):
        v = L[i]
        j = i - g
        while 0 <= j and v < L[j]:
            L[j+g] = L[j]
            j -= g
            cnt += 1
        L[j+g] = v


def shell_sort(L, n):
    global G
    for i in G:
        insertion_sort(L, n, i)

G = [i for i in [262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1] if i <= n]
shell_sort(A, n)

print(len(G))
print(' '.join(str(x) for x in G))
print(cnt)
for i in A:
    print(i)
### BUGGY CODE ###

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

a=0

for i in range(N):
  if A.count(A[0])>=2:
    print("NO")
    a=1
    break
  else:
    del A[0]

if a==0:
  print("YES")

 

### FIXED CODE ###

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

if len(A) == len(set(A)):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

S = input()

# 1以上の同じ色の石の列は1つに集約できる
T = S[0]
prev = T
for s in S[1:]:
    if prev != s:
        T += s
        prev = s

print(len(T) - 1)


### FIXED CODE ###

S = input()

# 1以上の同じ色の石の列は1つに集約できる
cnt = 1
prev = S[0]
for s in S[1:]:
    if prev != s:
        cnt += 1
        prev = s

print(cnt - 1)
### BUGGY CODE ###

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

ans = [True] * (n-k)
now = 1
for i in range(n):
    if i < k:
        now *= a[i]
        continue
    old = now
    now /= a[i-k]
    now *= a[i]
    ans[i-k] = now > old
for v in ans:
    print("Yes" if v else "No")


### FIXED CODE ###

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

i = k
# while i < k:
#     now *= a[i]
#     i += 1
while i < n:
    old = a[i-k]
    now = a[i]
    print("Yes" if now > old else "No")
    i += 1
    # old = now
    # now = (now / a[i-k]) * a[i]
    # print("Yes" if now > old else "No")
    # i += 1
### BUGGY CODE ###

import numpy as np
N,M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = int(1e9+7)
"""
dp[i][j] : S の i 文字目までと T の j 文字目までを考慮し、
この 2 文字 (S[i] と T[j]）をペアにするときの場合の数とすると、

dp[i][j] = (sum(dp[1:i-1][1:j-1]) + 1 if S[i] == T[j] else 0)
このsumの部分をどうもとめるか。

最終的な答えはsum(dp[:][:])。

2-D cumsumをつかう
i,j = 0のときにきをつけて
DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
"""

#dp = [[ 0 for _ in range(M)] for _ in range(N)]
dp = np.zeros((N,M), dtype = int)
# -1のIndexAccessをゼロにしたいので、ひとつ大きめに取っておく。
DS = np.zeros((N+1,M+1), dtype = int)

for i in range(N):
  for j in range(M):
    if S[i] != T[j]:
      dp[i, j] = 0
    else:
      dp[i, j] += 1
    ## 愚直ループを2次元部分和でなんとかする
    #for k in range(i):
    #  for l in range(j):
    #    dp[i][j] += dp[k][l]
    ## 愚直ループnp版。
      #dp[i,j] += np.sum(dp[:i, :j])
      dp[i,j] += DS[i-1,j-1]
      dp[i,j] %= mod
    DS[i,j] = DS[i-1,j] + DS[i,j-1] - DS[i-1,j-1] + dp[i,j]
    DS[i,j] %= mod
print(DS[-2][-2]+1)
#print(dp)
#print(DS)


### FIXED CODE ###

# numpyでかいてもTLEした。
# pypyでlistでかくととおる？

#import numpy as np
N,M = list(map(int, input().split()))
S = list(map(int, input().split()))
T = list(map(int, input().split()))
mod = int(1e9+7)
"""
dp[i][j] : S の i 文字目までと T の j 文字目までを考慮し、
この 2 文字 (S[i] と T[j]）をペアにするときの場合の数とすると、

dp[i][j] = (sum(dp[1:i-1][1:j-1]) + 1 if S[i] == T[j] else 0)
このsumの部分をどうもとめるか。

最終的な答えはsum(dp[:][:])。

2-D cumsumをつかう
i,j = 0のときにきをつけて
DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
"""

dp = [[ 0 for _ in range(M)] for _ in range(N)]
DS = [[ 0 for _ in range(M+1)] for _ in range(N+1)]

for i in range(N):
  for j in range(M):
    if S[i] != T[j]:
      dp[i][j] = 0
    else:
      dp[i][j] += 1
      dp[i][j] += DS[i-1][j-1]
      dp[i][j] %= mod
    DS[i][j] = DS[i-1][j] + DS[i][j-1] - DS[i-1][j-1] + dp[i][j]
    DS[i][j] %= mod
print(DS[-2][-2]+1)
#print(dp)
#print(DS)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
b = read().split()

sh -= 1; sw -= 1; gh -= 1; gw -= 1

#print(b)

from collections import deque

def nbd(nh,nw,cost,dv):
    if 0 <= nh < h and 0 <= nw < w and b[nh][nw]==".":
        dv += cost
        if dv < res[nh][nw]:
            res[nh][nw] = dv
            if cost: q.append((dv,nh,nw))
            else: q.appendleft((dv,nh,nw))
    return 


INF = 1<<30
res = [[INF]*w for _ in range(h)] #startからの最短距離
res[sh][sw] = 0
q = deque([(0,sh,sw)]) #(そこまでの距離、点)
while q:
    dv,vh,vw = q.popleft()
    if res[vh][vw] < dv: continue
    nbd(vh-1,vw,0,dv)
    nbd(vh,vw-1,0,dv)
    nbd(vh+1,vw,0,dv)
    nbd(vh,vw+1,0,dv)
    
    nbd(vh-1,vw-1,1,dv)
    nbd(vh-1,vw+1,1,dv)
    nbd(vh+1,vw-1,1,dv)
    nbd(vh+1,vw+1,1,dv)

    for i in range(-2,3):
        nbd(vh-2,vw+i,1,dv)
        nbd(vh+2,vw+i,1,dv)

    for i in range(-1,2):
        nbd(vh+i,vw-2,1,dv)
        nbd(vh+i,vw+2,1,dv)
    
    #print(res)
        
ans = res[gh][gw]
if ans != INF:
    print(ans)
else:
    print(-1)







### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
b = read().split()

sh -= 1; sw -= 1; gh -= 1; gw -= 1

#print(b)

from collections import deque

def nbd(nh,nw,dv):
    if dv < res[nh][nw]:
        res[nh][nw] = dv
        q.appendleft((dv,nh,nw))
    return 




INF = 1<<30
res = [[INF]*w for _ in range(h)] #startからの最短距離
res[sh][sw] = 0
q = deque([(0,sh,sw)]) #(そこまでの距離、点)
while q:
    dv,vh,vw = q.popleft()
    if res[vh][vw] < dv: continue
    if vh==gh and vw==gw: break
    
    if vh and b[vh-1][vw]==".":
        nbd(vh-1,vw,dv)
    if vw and b[vh][vw-1]==".":
        nbd(vh,vw-1,dv)
    if vh+1<h and b[vh+1][vw]==".":
        nbd(vh+1,vw,dv)
    if vw+1<w and b[vh][vw+1]==".":
        nbd(vh,vw+1,dv)
    
    for i in range(-2,3):
        nh = vh+i
        if nh < 0 or nh >= h: continue
        for j in range(-2,3):
            nw = vw + j
            if nw < 0 or nw >= w: continue
            if abs(i)+abs(j) > 1:
                if b[nh][nw] == "." and dv+1 < res[nh][nw]:
                    res[nh][nw] = dv+1
                    q.append((dv+1,nh,nw))


ans = res[gh][gw]
if ans != INF:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

# TLE が厳しすぎる

def accumulate(S1, S2):
    res = [0]
    c = 0
    for i in range(min(len(S1), len(S2))):
        if S1[i] == S2[i]:
            c += 1
        res.append(c)
    return res

inf = 2 * 10**9
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
C1 = C_T[0]
for C2 in C_T[1:]:
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    z1 = accumulate(C1, C2);  z1.reverse()
    Z1.append(z1)
    Z2.append([])
    for j in range(1, H+1):
        z1 = accumulate(C1, C2[j:]);  z1.reverse();  Z1.append(z1)
        z2 = accumulate(C1[j:], C2);  z2.reverse();  Z2.append(z2)
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + (Z1[j-k][k] if j>=k else Z2[k-j][j])
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
    C1 = C2
print(ans)


### FIXED CODE ###

# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)
### BUGGY CODE ###

import math 
from functools import reduce
def gcd(*numbers):
  return reduce(math.gcd,numbers)
K=int(input())
A=[]
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      s=gcd(i,j,k)
      A.append(s)
print(sum(A))

### FIXED CODE ###

import math
K=int(input())
ans=0
for a in range(1,K+1):
  for b in range(1,K+1):
    ans_=math.gcd(a,b)
    for c in range(1,K+1):
      ans+=math.gcd(ans_,c)
print(ans)
### BUGGY CODE ###

import bisect

N = int(input())
L = sorted(map(int, input().split()))

S = 0
for i in range(N):
    a = L[i]
    for k in range(i - 1):
        c = L[k]
        for j in range(i - 1, k, -1):
            b = L[j]
            if a < b + c:
                S += 1
            else:
                break
print(S)


### FIXED CODE ###

import bisect
import random

def test(L):
    lst = []
    N = len(L)
    for a in range(N):
        for b in range(a):
            for c in range(b):
                if L[a] < L[b] + L[c]:
                    lst.append((c, b, a))
    return lst

def test_len(L):
    return len(test(L))

def test2(L):
    return len(set((l[0], l[2]) for l in test(L)))

N = int(input())
L = sorted(map(int, input().split()))
# L = [1, 1, 1000]
# L = [218, 233, 389, 645, 704, 728, 786]
# N = 10
# L = sorted([random.randint(0, 1000) for _ in range(N)])
# L = [150, 190, 192, 281, 294, 374, 501, 686, 769, 954]
# print(L)
# N = len(L)
S = 0
for a in range(2, N):
    c = bisect.bisect_left(L, (L[a] + 2) // 2)
    while c >= 0:
        if L[a] < L[c] * 2:
            c -= 1
        else:
            break
    b = c + 1
    assert L[a] < L[b] * 2
    if b == 0:
        # print("b0", b, a, (a - 1) * (a) // 2)
        S += (a - 1) * (a) // 2
        continue
    if c >= a - 1:
        continue
    assert L[a] < L[b] + L[b]
    assert L[a] >= L[c] + L[c], (a, c)
    S += (a - b) * (a - b - 1) // 2
    while c >= 0:
        while L[a] >= L[b] + L[c]:
            b += 1
        assert L[a] < L[b] + L[c]
        assert L[a] >= L[b - 1] + L[c]
        # print(c, b, a)
        S += a - b
        c -= 1
print(S)
# print(test_len(L))
### BUGGY CODE ###

from collections import deque
n = int(input())
nd = deque(map(int, input().split()))
c = 0
for i in range(n):
    s = nd.popleft()
    for k in nd:
        if (k < s):
            c += 1
    
print(c)


### FIXED CODE ###

n = int(input())
nlist = list(map(int, input().split()))
W = [0for i in range(n)]
def M(l,r):      ##l~r-1 까지의 리스트.
    if (l+1 >= r):
        return 0
    elif (l+2 == r):
        if (nlist[l] <= nlist[l+1]):
            return 0
        else:
            nlist[l],nlist[l+1] = nlist[l+1],nlist[l]
            return 1
    ##위의 if문으로 (r-l)가 2이하일 경우는 해놓음
    m = (l+r)//2
    i = l
    j = m
    k = l
    cl = M(l,m)
    cr = M(m,r)
    c = 0
    while (i<m and j<r):
        if (nlist[i] <= nlist[j]):
            W[k] = nlist[i] ##l부터 r까지 W에 크기순으로 대입해나감
            k += 1
            i += 1
        else:
            W[k] = nlist[j]  ##일단 W[k]에는 더 작은쪽을 저장하는듯
            k += 1
            j += 1
            c += (m-i)  ##만약 nlist[i] > nlist[j]라면 i~m-1 까지 반전 하고있기 때문
                        ##그러고 더 작은 nlist[j]를 안에 넣는것.
    while (i<m):   ##i번째쪽에 더 큰것들이 남았을 경우 (j=r 이 되있는 상황이기에 더 반전수를 늘리지는 않음)
        W[k] = nlist[i]
        k += 1
        i += 1
    while (j<r):   ##j쪽에 큰게 남아있는경우도 동일
        W[k] = nlist[j]
        k += 1
        j += 1
    for i in range(l,r): 
        nlist[i] = W[i]
    return cl+cr+c
        
print(M(0,n))