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

N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                calculateList = [abs(j + 1 - i),
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answer = min(calculateList)
                answerList[answer] = answerList[answer] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])


### FIXED CODE ###

N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                calculateList = [abs(j + 1 - i),
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answer = min(calculateList)
                answerList[answer] = answerList[answer] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])
### BUGGY CODE ###

import heapq

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sorted_A = []
A_q = Heapq(A, True)
for i in range(min(X, K)):
    sorted_A.append(A_q.pop())
sorted_B = []
B_q = Heapq(B, True)
for i in range(min(Y, K)):
    sorted_B.append(B_q.pop())
sorted_C = []
C_q = Heapq(C, True)
for i in range(min(Z, K)):
    sorted_C.append(C_q.pop())
# pop_c_list = []
# pop_b_list = []
#
# max_list = []
# for i in range(min(X, K)):
#     a = A_q.pop()
#     for j in range(min(Y, K)):
#         b = B_q.pop()
#         pop_b_list.append(b)
#         for k in range(min(Z, K)):
#             c = C_q.pop()
#             pop_c_list.append(c)
#             max_list.append(a+b+c)
#         for pop_c in pop_c_list:
#             C_q.push(pop_c)
#     for pop_b in pop_b_list:
#         B_q.push(pop_b)

# A.sort(reverse=True)
# B.sort(reverse=True)
# C.sort(reverse=True)

max_list = []
for a in sorted_A:
    for b in sorted_B:
        for c in sorted_C:
            max_list.append(a + b + c)

max_list_q = Heapq(max_list, True)
for i in range(K):
    print(max_list_q.pop())

### FIXED CODE ###

import heapq

import itertools

class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq) * self.sign

    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)

    def top(self):
        return self.hq[0] * self.sign

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
C.sort(reverse=True)

p = itertools.product(A, B)
A_B_list = [sum(v) for v in itertools.product(A, B)]
A_B_list.sort(reverse=True)
A_B_C_list = [sum(v) for v in itertools.product(A_B_list[:3000], C[:3000])]
A_B_C_list.sort(reverse=True)

for ans in A_B_C_list[:K]:
    print(ans)
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
A = list()
B = list()
x = 0
A = [2**100+i for i in range(N+1)]
for i in range(K, N+2):
    a = itertools.combinations(A,i)
    for s in a:
        B.append(sum(s))
print(len(list(set(B)))%(10**9+7))


### FIXED CODE ###

N,K = map(int,input().split())
sum = 0
for i in range(K, N+2):
    sum += i * (N - i + 1) + 1
print(sum % (10**9+7))
### BUGGY CODE ###

char_num = int(input())
char_length = 10
chars = []
for i in range(char_num):
    chars.append(input())


class CharArrange:
    def __init__(self, char):
        self.char = char

    def char_run(self):
        list_char = self.str2ord_list(self.char)
        for pos in range(1, len(list_char)):
            self.insert_sort(list_char, pos, list_char[pos])
        self.char = self.ordList2Str(list_char)

    def order_run(self, chars):
        for i, char in enumerate(chars):
            chars[i] = self.ord_list2ord_concat(self.str2ord_list(char))
        for pos in range(len(chars)):
            self.insert_sort(chars, pos, chars[pos])
        self.ord_chars = chars

    def str2ord_list(self, char):
        return list(map(ord, char))

    def ordList2Str(self, ordList):
        return ''.join(list(map(chr, ordList)))

    def ord_list2ord_concat(self, ord_list):
        self.ord_concat = ''
        for ord_num in ord_list:
            self.ord_concat += str(ord_num)
        return int(self.ord_concat)

    def insert_sort(self, A, pos, value):
        i = pos - 1
        while (i >= 0 and A[i] > value):
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = value
        return A


for i, char in enumerate(chars):
    CA = CharArrange(char)
    CA.char_run()
    chars[i] = CA.char
CA.order_run(chars)
ord_chars = CA.ord_chars

counter = 0
for i in range(len(ord_chars) - 1):
    k = i + 1
    while (ord_chars[i] == ord_chars[k]):
        counter += 1
        if k == len(ord_chars) - 1:
            break
        else:
            k += 1
print(counter)


### FIXED CODE ###

char_num = int(input())
char_length = 10
chars = []
for i in range(char_num):
    chars.append(input())


class CharArrange:
    def __init__(self, char):
        self.char = char

    def char_run(self):
        list_char = self.str2ord_list(self.char)
        for pos in range(1, len(list_char)):
            self.insert_sort(list_char, pos, list_char[pos])
        self.char = self.ordList2Str(list_char)

    def order_run(self, chars):
        for i, char in enumerate(chars):
            chars[i] = self.ord_list2ord_concat(self.str2ord_list(char))
        for pos in range(len(chars)):
            self.insert_sort(chars, pos, chars[pos])
        self.ord_chars = chars

    def str2ord_list(self, char):
        return list(map(ord, char))

    def ordList2Str(self, ordList):
        return ''.join(list(map(chr, ordList)))

    def ord_list2ord_concat(self, ord_list):
        self.ord_concat = ''
        for ord_num in ord_list:
            self.ord_concat += str(ord_num)
        return int(self.ord_concat)

    def insert_sort(self, A, pos, value):
        i = pos - 1
        while (i >= 0 and A[i] > value):
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = value
        return A


counter = 0
hash_table = {}
for i, char in enumerate(chars):
    CA = CharArrange(char)
    CA.char_run()
    if CA.char in hash_table:
        hash_table[CA.char] += 1
    else:
        hash_table[CA.char] = 0
    counter += hash_table[CA.char]


print(counter)
### BUGGY CODE ###

import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [[float('inf') for _ in range(H + max(AB)[0] + 1)] for _ in range(N + 1)]
dp[0][0] = 0
for n in range(N):
    for h in range(H + max(AB)[0] + 1):
        if h - AB[n][0] >= 0:
            dp[n + 1][h] = min(dp[n + 1][h - AB[n][0]] + AB[n][1], dp[n][h])
        else:
            dp[n + 1][h] = dp[n][h]

print(min(dp[N][H:]))


### FIXED CODE ###

import sys

H, N = map(int, input().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dp = [0 for _ in range(H + max(AB, key=lambda x: x[0])[0])]
for h in range(1, len(dp)):
    dp[h] = min(dp[h-a] + b for a, b in AB)

print(dp[H])
### BUGGY CODE ###

N = int(input())
A = list(map(lambda x:int(x)-1,input().split()))
ans = 0
paired = []
for i in range(N):
    if i in paired:
        continue
    else:
        if A[A[i]] == i:
            ans += 1
            paired.append(i)
            paired.append(A[i])
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(lambda x:int(x)-1,input().split()))
ans = 0
paired = []
flag = [0]*N
for i in range(N):
    if flag[i]:
        continue
    else:
        if A[A[i]] == i:
            ans += 1
            flag[A[i]] = 1
print(ans)
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

max = sum(p[:k])
idx = 0
for i in range(1, n-k+1):
    if max < sum(p[i:i+k]):
        max = sum(p[i:i+k])
        idx = i

result = 0
for i in range(k):
    result += sum(range(1,p[idx+i]+1))/p[idx+i]

print(result)


### FIXED CODE ###

n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]

cum = [0]
for i in range(1, n+1):
    cum.append(cum[i-1] + (p[i-1]+1)/2)

res = 0
for i in range(0, n-k+1):
    val = cum[i+k] - cum[i]
    if res < val:
        res = val

print(res)
### BUGGY CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

d = [e1+e2 for e1 in a for e2 in b]
d.sort(reverse=True)
d = d[:k]

e = [e1+e2 for e1 in d for e2 in c]    
e.sort(reverse=True)

for i in range(k):
  print(e[i])

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []

for e1 in a:
  for e2 in b:
    d.append(e1+e2)

d.sort(reverse=True)
d = d[:k]
e = []

for e1 in d:
  for e2 in c:
    e.append(e1+e2)
    
e.sort(reverse=True)

for i in range(k):
  print(e[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N)]

Now=[0 for _ in range(N+1)]

day=0
goal_person=0

while True:
	flag=False
	Visit=defaultdict(lambda: None) 
	for me in range(1,N+1):
		now=Now[me]
		if now<N-1:	#現在値がN-1になっていたら、もうアガリ
			opponent=A[me][now]

			opponentnow=Now[opponent]
			opp_of_opp=A[opponent][opponentnow]

			if me==opp_of_opp and Visit[me] is None and Visit[opponent] is None:
				flag=True	#前進フラグ　1回前よりも状態が進めばTrueになる
				Now[me]+=1
				Now[opponent]+=1
				Visit[me]=1
				Visit[opponent]=1
				if Now[me]==N-1:		goal_person+=1
				if Now[opponent]==N-1:	goal_person+=1

	else:
			if not flag:
				print -1
				quit()
	day+=1

	if goal_person==N:
		print day
		quit()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	game.add((a,b))

day=0

while game:
	next_game=set()
	Visit=defaultdict(lambda: None) 

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp) and Visit[x] is None and Visit[y] is None:
			Visit[x]=1
			Visit[y]=1
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))

	game=next_game
	day+=1


for i in range(1,N+1):
	if Now[i] != N-2:
		print -1
		quit()
else:
	print day
### BUGGY CODE ###

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

data = []
for a,b in ab:
  if a == 1:
    if b in data:
      print("POSSIBLE")
      break
    else:
      data.append(b)
  if b == N:
    if a in data:
      print("POSSIBLE")
      break
    else:
      data.append(a)
else:
  print("IMPOSSIBLE")


### FIXED CODE ###

import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()

data = [0]*N
for i in range(M):
  a,b = IL()
  if a == 1:
    if data[b]==1:
      print("POSSIBLE")
      break
    else:
      data[b]=1
  if b == N:
    if data[a]==1:
      print("POSSIBLE")
      break
    else:
      data[a]=1
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

n,k,l=map(int,input().split())
def maketree(n,k):
    from collections import defaultdict
    road=defaultdict(set)
    roadidx=[-1 for _ in range(n)]
    for i in range(k):
        p,q=map(int,input().split())
        p-=1
        q-=1
        pidx=roadidx[p]
        qidx=roadidx[q]
        if pidx==-1 and qidx==-1:
            road[p]={p,q}
            roadidx[p]=p
            roadidx[q]=p
        elif pidx==-1 and qidx!=-1:
            road[qidx]|={p,}
            roadidx[p]=qidx
        elif pidx!=-1 and qidx==-1:
            road[pidx]|={q,}
            roadidx[q]=pidx
        elif pidx!=qidx:
            road[pidx]=road[pidx]|road[qidx]
            for j in road[qidx]:
                roadidx[j]=pidx
            road.pop(qidx)
    return road,roadidx

roadtree,roadidx=maketree(n,k)
metrotree,metroidx=maketree(n,l)

result=[1 for i in range(n)]
for i in roadtree:
    target=roadtree[i]
    check=target.copy()
    while len(check)>0:
        now=check.pop()
        if metroidx[now]!=-1:
            x=target & metrotree[metroidx[now]]
            if len(x)!=0:
                for j in x:
                    result[j]=len(x)
        else:x={now,}
        check-=x

res=''
for i in range(n):
    res=res+str(result[i])+' '
print(res)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,K,L=map(int,input().split())
road=[tuple(map(int,input().split())) for _ in range(K)]
metro=[tuple(map(int,input().split())) for _ in range(L)]
inf=float('inf')
def Find(root,x):
    if root[x]<0:
        return x
    if root[x]>=0:
        root[x]=Find(root,root[x])
        return root[x]

def UnionFind(N,branch):
    root=[-1]*(N+1)
    for a,b in branch:
        aroot=Find(root,a)
        broot=Find(root,b)
        if aroot==broot:continue
        elif root[aroot]<=root[broot]:
            root[aroot]+=root[broot]
            root[broot]=aroot
        elif root[aroot]>root[broot]:
            root[broot]+=root[aroot]
            root[aroot]=broot
    return root
r_root=UnionFind(N,road)
m_root=UnionFind(N,metro)
from collections import defaultdict
data=[]
cnt=defaultdict(int)
for i in range(1,N+1):
    ri=Find(r_root,i)
    mi=Find(m_root,i)
    data.append((ri,mi))
    cnt[(ri,mi)]+=1
ans=''
for d in data:
    ans+=str(cnt[d])+' '
print(ans[:-1])
### BUGGY CODE ###

import fractions
import itertools
n = int(input())
l = [int(i) for i in input().split()]

m = list(itertools.combinations(l,2))

m = [fractions.gcd(i[0],i[1]) for i in m]

print(min(m))

### FIXED CODE ###

import fractions
n = int(input())
l = [int(i) for i in input().split()]
ans = l[0]
for i in range(n):
    ans = fractions.gcd(ans,l[i])

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

import collections

H,W,M = map(int, input().split())
h = [0]*M
w = [0]*M
for i in range(M):
    h[i], w[i] = map(int, input().split())
ch = collections.Counter(h).most_common()
mh = []
mnh = ch[0][1]
for ch1 in ch:
    if mnh == ch1[1]:
        mh.append(ch1[0])
        continue
    else:
        break
    break
cw = collections.Counter(w).most_common()
mw = []
mnw = cw[0][1]
for cw1 in cw:
    if mnw == cw1[1]:
        mw.append(cw1[0])
        continue
    else:
        break
    break
hw = list(zip(h,w))
for h1 in mh:
    for w1 in mw:
        if (h1,w1) not in hw:
            print(mnh+mnw)
            exit()
print(mnh+mnw-1)

### FIXED CODE ###

from collections import defaultdict

H, W, M = map(int, input().split())
h = [0] * M
w = [0] * M

nh = [0] * H  # number of h == i+1
nw = [0] * W  # number of w == i+1
dic = defaultdict(bool)

for i in range(M):
    h[i], w[i] = map(int, input().split())
    h[i] -= 1
    w[i] -= 1
    nh[h[i]] += 1
    nw[w[i]] += 1
    dic["{}-{}".format(h[i],w[i])] = True

mnh = max(nh)
mnw = max(nw)

mh = [i for i, nh1 in enumerate(nh) if nh1 == mnh]
mw = [i for i, nw1 in enumerate(nw) if nw1 == mnw]

for h1 in mh:
    for w1 in mw:
        if not dic["{}-{}".format(h1,w1)]:
            print(mnh + mnw)
            exit()
print(mnh + mnw - 1)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
c=[]
for i in range(n-1):
  if s[i:i+2]=='AC':
    c.append(1)
  else:
    c.append(0)
for i in range(q):
  l,r=map(int,input().split())
  print(sum(c[l-1:r-1]))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
c=[0 for _ in range(n)]
p=''
d=0
for i in range(n):
  x=s[i]
  if p=='A' and x=='C':
    d+=1
  p=x
  c[i]=d
for i in range(q):
  ans=0
  l,r=map(int,input().split())
  ans=c[r-1]-c[l-1]

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

N = int(input())
P = [int(x) for x in input().split()]
Count = 1
for T in range(1,N):
    if P[T]<min(P[:T]):
        Count += 1
print(Count)

### FIXED CODE ###

N = int(input())
P = [int(x) for x in input().split()]
Count = 1
MIN = P[0]
for T in range(1,N):
    if P[T]<MIN:
        MIN = P[T]
        Count += 1   
print(Count)
### BUGGY CODE ###

s = input()
K = int(input())
ab = 'abcdefghijklmnopqrstuvwxyz'
N = len(s)
substrings = set()
for i in ab:
    for l in range(N):
        if s[l] != i:
            continue
        for r in range(l,N):
            substrings.add(s[l:r+1])
    if len(substrings) >= K:
        break

substrings = list(substrings)
substrings.sort()
print(substrings[K-1])

### FIXED CODE ###

s = input()
K = int(input())
ab = 'abcdefghijklmnopqrstuvwxyz'
N = len(s)
substrings = set()
for i in ab:
    for l in range(N):
        if s[l] != i:
            continue
        for r in range(l,N):
            if r-l+1 > K:
                break
            substrings.add(s[l:r+1])
    if len(substrings) >= K:
        break
substrings = list(substrings)
substrings.sort()
print(substrings[K-1])
### BUGGY CODE ###

N = int(input())
b = [int(num) for num in input().split()]
queue = [[b,[]]]

def bfs(queue):
    c,prev = queue.pop(0)
    ret = 0
    l = len(c)
    for i in range(l):
        if c[i] == i+1:
            app = []
            if i==0:
                app = c[1:]
            elif i==l:
                app = c[:-1]
            else:
                app = c[:i] + c[i+1:]
            pr = [i+1] + prev
            if app == []:
                ret = 1
            queue.append([app,pr])
    return queue

ans = -1
while queue != []:
    if queue[-1][0] == []:
        ans = queue[-1]
        break
    queue = bfs(queue)
        
if ans == -1:
    print(ans)
else:
    for num in ans[1]:
        print(num)
        




### FIXED CODE ###

N = int(input())
b = [int(num) for num in input().split()]
queue = [[b,[]]]

def bfs(queue):
    c,prev = queue.pop(0)
    cnt = len(c)-1
    while cnt >= 0:
        if c[cnt] == cnt+1:
            del c[cnt]
            prev = [cnt+1] + prev
            queue.append([c,prev])
            break
        cnt -= 1
    return queue

ans = -1
while queue != []:
    if queue[-1][0] == []:
        ans = queue[-1]
        break
    queue = bfs(queue)
        
if ans == -1:
    print(ans)
else:
    for num in ans[1]:
        print(num)
### BUGGY CODE ###

n=int(input())
counter_2=0
counter_5=0

def count_2(num):
    cnt=0
    while num%2==0:
        num//=2
        cnt+=1
    return cnt
def count_5(num):
    cnt=0
    while num%5==0:
        num//=5
        cnt+=1
    return cnt

while n>=2:
    counter_2+=count_2(n)
    counter_5+=count_5(n)
    n-=2

print(min(counter_2,counter_5))


### FIXED CODE ###

n=int(input())
ans=0
keta=10

def count_2(num):
    return format(num, 'b')[::-1].find('1')

if n%2==1:
    print(0)
else:
    while n//keta!=0:
        ans+=n//keta
        keta*=5
    print(ans)
### BUGGY CODE ###

from collections import deque
S=input()
Q=int(input())
query=[list(map(str,input().split())) for _ in range(Q)]

ans=deque(S)
for i,q in enumerate(query):
  if len(q)==1:
    ans.reverse()
  else:
    _,f,c=q
    if f=='1':
      ans.appendleft(c)
    else:
      ans.append(c)
print(*ans,sep='')

### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
query=[list(map(str,input().split())) for _ in range(Q)]

ans=deque(S)
reverse=False
for i,q in enumerate(query):
  if len(q)==1:
    reverse=not reverse
  else:
    _,f,c=q
    if (f=='2') ^ reverse:
      ans.append(c)
    else:
      ans.appendleft(c)
if reverse:
  print(*reversed(ans),sep='')
else:
  print(*ans,sep='')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9 + 7)
ans = 10 ** 9 + 7
def solve(x, y, cnt):
    global ans
    if x == w - 1 and y == h - 1:
        if field[y][x] == "#":
            cnt += 1
        ans = min(ans, cnt)
        return

    if 0 <= x < w and 0 <= y < h:
        if field[y][x] == "#":
            solve(x + 1, y, cnt + 1)
            solve(x, y + 1, cnt + 1)
        else:
            solve(x + 1, y, cnt)
            solve(x, y + 1, cnt)
    else:
        return

h, w = map(int, input().split())
field = []

for i in range(h):
    field.append(list(input()))

solve(0, 0, 0)
print(ans)


### FIXED CODE ###

h, w = map(int, input().split())
field = []

for i in range(h):
    field.append(list(input()))

dp = [[0 for i in range(w)] for j in range(h)]

for i in range(1, w):
    if field[0][i - 1] == field[0][i]:
        dp[0][i] = dp[0][i - 1] 

    else:
        if field[0][i - 1] == "." and field[0][i] == "#":
            dp[0][i] = dp[0][i - 1] + 1
        else:
            dp[0][i] = dp[0][i - 1]

for i in range(1, h):
    if field[i][0] == field[i - 1][0]:
        dp[i][0] = dp[i - 1][0]
    else:
        if field[i - 1][0] == "." and field[i][0] == "#":
            dp[i][0] = dp[i - 1][0] + 1
        else:
            dp[i][0] = dp[i - 1][0]

for y in range(1, h):
    for x in range(1, w):
        dp[y][x] = min(dp[y - 1][x] + (1 if field[y][x] != field[y - 1][x] and field[y - 1][x] == "." else 0), dp[y][x - 1] + (1 if field[y][x] != field[y][x - 1] and field[y][x - 1] == "."  else 0))

print(dp[h - 1][w - 1] + (1 if field[0][0] == "#" else 0))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

next_num = {
  0:(1, 0), 1:(1, 2), 2:(1, 4), 3:(1, 6), 4:(1, 8),
  5:(2, 1), 6:(2, 3), 7:(2, 5), 8:(2, 7), 9:(2, 9)
}
memo = {}
def rec_calc(d, c):
  global memo
  if (d, c) in memo:
    return memo[(d, c)]
  if c == 1:
    memo[(d, c)] = (0, d)
    return (0, d)
  elif c == 2:
    n = 2 * d
    if n <= 9:
      memo[(d, c)] = (1, n)
      return (1, n)
    else:
      a1 = n % 10
      a2 = n // 10
      memo[(d, c)] = (2, a1+a2)
      return (2, a1+a2)
  else:
    t, nn = next_num[d]
    time, n = rec_calc(nn, c//2)
    if c % 2 == 0:
      res = ((c//2)*t + time, n)
      memo[(d, c)] = res
      return res
    else:
      n += d
      if n <= 9:
        res = ((c//2)*t+time+1, n)
        memo[(d, c)] = res
      else:
        a1 = n % 10
        a2 = n // 10
        res = ((c//2)*t+time+2, a1+a2)
        memo[(d, c)] = res
      return res

M = int(input())
ans = 0
D = []
for i in range(M):
  d, c = map(int, input().split())
  time, n = rec_calc(d, c)
  ans += time
  D.append(n)

d1 = D.pop()
while D:
  d2 = D.pop()
  n = d1 + d2
  if n <= 9:
    ans += 1
    d1 = n
  else:
    ans += 2
    d1 = (n%10) + (n//10)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

m = int(input())

sum_n = 0
len_n = 0
for i in range(m):
    d,c = map(int, input().split())
    sum_n += d*c
    len_n += c

ans = len_n-1 + (sum_n-1)//9
print(ans)
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = collections.Counter(a)
v = list(d.values())
v = sorted(v)
ans = 0

while len(v) > k:
    ans += v.pop(0)

print(ans)


### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = collections.Counter(a)
v = list(d.values())
v = sorted(v)

ans = 0
i = 0
while len(v) - i > k:
    ans += v[i]
    i += 1

print(ans)