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

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in range(10**9) :
    if i not in A : continue
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N * 0.99 - 1 : break

for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-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 ###

from collections import deque
import copy
def bfs():
  H, W = map(int, input().split())
  maze = [list(input()) for i in range(H)]
  S = []
  for i in range(H):
    for j in range(W):
      if maze[i][j] == ".":
        maze[i][j] = float("inf")
        S.append([i, j])
      else:
        maze[i][j] = -1
  ans = 0
  for k in range(len(S)):
    maze1 = copy.deepcopy(maze)
    maze1[S[k][0]][S[k][1]] = 0
    q = deque()
    q.append([S[k][0],S[k][1]])
    while len(q)>0:
      y, x = q.popleft()
      for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nexty = y+i
        nextx = x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        if maze1[nexty][nextx] != -1:
          if maze1[nexty][nextx] > maze1[y][x]:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs()

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()
### BUGGY CODE ###

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()))
XYZ=[]
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
for a in range(1,X+1):
    for b in range(1,Y+1):
        for c in range(1,Z+1):
            if(a*b*c)<=K:
                XYZ.append(A[a-1]+B[b-1]+C[c-1])
XYZ.sort(reverse=True)
for xyz in XYZ[:K]:
    print(xyz)

### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])
### BUGGY CODE ###

import heapq
def SME(Whole,start,end,L,ANS):
    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 and idx < end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N -50 : 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()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 2 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
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 ###

import numpy as np
N, M, Q = map(int, input().split())
table = np.zeros((N, N), np.int64)
for _ in range(M):
    L, R = map(lambda n: int(n) - 1, input().split())
    table[L][R] += 1
table = np.rot90(np.rot90(table, k=-1).cumsum(axis=0).cumsum(axis=1), k=1)
for _ in range(Q):
    p, q = map(lambda n: int(n) - 1, input().split())
    print(table[p][q])

### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())
table = np.zeros((N, N), np.int64)
for _ in range(M):
    L, R = map(lambda n: int(n) - 1, input().split())
    table[L][R] += 1
table = np.rot90(np.rot90(table, k=-1).cumsum(axis=0).cumsum(axis=1), k=1)
for _ in range(Q):
    p, q = map(lambda n: int(n) - 1, input().split())
    print(table[p][q])
### BUGGY CODE ###

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

flg = 'YES'
for i,a in enumerate(A):
    if a in A[i+1:]:
        flg = 'NO'
        break

print(flg)

### FIXED CODE ###

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

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

N = int(input())
a = [0] + [int(input()) for _ in range(N)]
preid = 1
ans = 0
while True:
    tmp = preid
    ans += 1
    if a[preid] == 2:
        print(ans)
        break
    preid = a[preid]
    if a[tmp] == a[preid]:
        print(-1)
        break


### FIXED CODE ###

N = int(input())
a = [0] + [int(input()) for _ in range(N)]
ans = 0
idx = 1
flag = False
for i in range(N):
    ans += 1
    if a[idx] == 2:
        print(ans)
        flag = True
        break
    idx = a[idx]
else:
    print(ans if flag else -1)
### BUGGY CODE ###

N=int(input())
S=str(input())

r=S.count('R')
g=S.count('G')
b=S.count('B')


ans=r*g*b
dib=0

for i in range(N-2):
    for j in range(i+1,N-1):
            dib=j-i
            if j+dib<=N-1:
                if S[i]!=S[j] and S[i]!=S[j+dib] and S[j]!=S[j+dib]:
                    ans=ans-1
            
print(ans)


### FIXED CODE ###

N=int(input())
S=str(input())

r=S.count('R')
g=S.count('G')
b=S.count('B')


ans=r*g*b
dib=0
m=0

for i in range(N-2):
    m=(N+i)//2+1
    for j in range(i+1,m):
            dib=j-i
            if j+dib<=N-1:
                if S[i]!=S[j] and S[i]!=S[j+dib] and S[j]!=S[j+dib]:
                    ans=ans-1
            
print(ans)
### BUGGY CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

l = ins()
a = l
n = len(l)
x = 3 if a[n-1]=='1' else 1
#for i in range(1,n):
for i in range(n-2,-1,-1):
    if a[i]=='1':
        x = (2*x+3**(n-1-i))
        if x>=R:
            x -= R
print(x%R)


### FIXED CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

l = ins()
a = l[::-1]
n = len(l)
x = 3 if a[0]=='1' else 1
for i in range(1,n):
    if a[i]=='1':
        x = (2*x+pow(3,i,R))%R
print(x)
### BUGGY CODE ###

N = int(input())

uvw= [[int(i) for i in input().split()] for _ in range(N-1)]

def dfs() :
	paint = [-1] * (N + 1)
	
	queue = [1]
	paint[1] = 1

	while queue :
		current = queue.pop(0)

		for u, v, w in uvw :
			if v == current :
				u, v = v, u

			if u == current and paint[v] == -1 :
				queue.append(v)
				paint[v] = (paint[u] + w) % 2

	return paint[1:]

for i in dfs() :
	print(i)

### FIXED CODE ###

N = int(input())

uvw= [[int(i) for i in input().split()] for _ in range(N-1)]

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

for u, v, w in uvw :
    path[u].append((v, w))
    path[v].append((u, w))

paint = [0] * (N + 1)

queue = [1]
visited = [False] * (N + 1)

while queue :
    current = queue.pop(0)
    w = paint[current]

    for destination, w_ in path[current] :
        if not visited[destination] :
            paint[destination] = (w + w_) & 1
            queue.append(destination)
            visited[destination] = True

for i in paint[1:] :
    print(i)
### BUGGY CODE ###

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

l = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    x,y = map(int, input().split())
    l[x-1][y-1] = 1
    l[y-1][x-1] = 1

connect = []
v = []

for i in range(n):
    if i not in v:
        connect.append([i])
        v.append(i)
        stack =[i]
        visited = [i]
        while stack:
            q = stack.pop()
            for j in range(n):
                if l[q][j]==1 and j not in visited:
                    connect[-1].append(j)
                    visited.append(j)
                    stack.append(j)
                    v.append(j)

a = []
for i in range(len(connect)):
    a.append([])
    for j in connect[i]:
        a[-1].append(p[j]-1)

ans = 0

for i in range(len(connect)):
    ans += len(set(a[i]) & set(connect[i]))

print(ans)


### FIXED CODE ###

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

l = [[] for j in range(n)]

for i in range(m):
    x,y = map(int, input().split())
    l[x-1].append(y-1)
    l[y-1].append(x-1)

connect = []
a = []
v = [0 for i in range(n)]

for i in range(n):
    if v[i] == 0:
        connect.append([i])
        a.append([p[i]-1])
        v[i]=1
        stack =[i]
        while stack:
            q = stack.pop()
            for j in range(len(l[q])):
                if v[l[q][j]]==0:
                    connect[-1].append(l[q][j])
                    a[-1].append(p[l[q][j]]-1)
                    stack.append(l[q][j])
                    v[l[q][j]]=1

ans = 0

for i in range(len(connect)):
    ans += len(set(a[i]) & set(connect[i]))

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

# 初期入力
N = int(input())
AB = [list(map(int, input().split())) for i in range(N-1)]

#　頂点をキー、つながり先をVALUEの辞書
tunagari ={}
for ab in AB:
    tunagari.setdefault(ab[0], []).append(ab[1])
    tunagari.setdefault(ab[1], []).append(ab[0])

# 　最小の色数（根の辺の数）
color_count = [len(i) for i in tunagari.values() ]
color_max =max(color_count)     
print(color_max) #答え

#
color_set =set("")
#頂点とつながり先をキー、色をValueの辞書
color_ten_ten = {}
from collections import defaultdict
col_sumi= {i:set() for i in tunagari.keys()} # 使った色を覚えておく辞書

for k,v in tunagari.items():
    color_set =set([i for i in range(1,color_max+1) ])
    for ii in v:
        if (col_sumi[k] & color_set) and (k<ii) :
            color_set = color_set - col_sumi[k] # 今の頂点に対して覚えていた色を消す
        if (col_sumi[ii] & color_set) and (k<ii):    
            color_set =color_set - col_sumi[ii] # 先の頂点に対して覚えていた色を消す
        if k<ii:
            xx = color_set.pop() # ポップだから速度のため末尾から消す  
            color_ten_ten.setdefault((k,ii) ,xx)  
            col_sumi[k].add(xx) # 元の頂点に対して使った色を覚えておく
            col_sumi[ii].add(xx) # 後の頂点に対して使った色を覚えておく

#AB＝color_ten_tenのキーが同じなら、値の色をprint
for i in AB:
    ab = tuple(i)
    if ab in color_ten_ten.keys() :
        print(color_ten_ten[ab])

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
### BUGGY CODE ###

K = int(input())
S = input()
N = len(S)

MOD = 10**9+7
n = N+K
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

ans = 0
for i in range(K+1):
    ans += pow(26, K-i, MOD) * pow(25, i, MOD) * comb(N+i-1, i)
    ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 10**9+7
K = int(input())
S = input()
N = len(S)

n = N+K
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

ans = 0
for i in range(K+1):
    ans += pow(26, K-i, MOD) * pow(25, i, MOD) * comb(N+i-1, i)
    ans %= MOD
print(ans)
### BUGGY CODE ###

h,n = map(int,input().split())
l = []
k = 0
for i in range(n):
    a,b = map(int,input().split())
    l.append([a,b])
    k += a
ans = 0
i = 0
dp = [0 for i in range(h+1)]
for i in range(n):
    a,b = l[i]
    for j in range(h):
        if j+a <= h:
            if j == 0:
                if dp[j+a] == 0:
                    dp[j+a] = b
                else:
                    dp[j+a] = min(b,dp[j+a])
            else:
                if dp[j] != 0:
                    if dp[j+a] == 0:
                        dp[j+a] = dp[j] + b
                    else:
                        dp[j+a] = min(dp[j]+b,dp[j+a])
        else:
            if dp[j] != 0:
                if dp[h] == 0:
                    dp[h] = dp[j]+b
                else:
                    dp[h] = min(dp[h],dp[j]+b)
            else:
                if j == 0:
                    if dp[h] == 0:
                        dp[h] = dp[j]+b
                    else:
                        dp[h] = min(dp[h],dp[j]+b)
print(dp[h])

### FIXED CODE ###

h,n = map(int,input().split())
l = []
k = 0
for i in range(n):
    a,b = map(int,input().split())
    l.append([a,b])
    k += a
ans = 0
i = 0
dp = [0 for i in range(h+1)]
for i in range(n):
    a,b = l[i]
    for j in range(h):
        if j+a <= h:
            if j == 0:
                if dp[j+a] == 0:
                    dp[j+a] = b
                else:
                    dp[j+a] = min(b,dp[j+a])
            else:
                if dp[j] != 0:
                    if dp[j+a] == 0:
                        dp[j+a] = dp[j] + b
                    else:
                        dp[j+a] = min(dp[j]+b,dp[j+a])
        else:
            if dp[j] != 0:
                if dp[h] == 0:
                    dp[h] = dp[j]+b
                else:
                    dp[h] = min(dp[h],dp[j]+b)
            else:
                if j == 0:
                    if dp[h] == 0:
                        dp[h] = dp[j]+b
                    else:
                        dp[h] = min(dp[h],dp[j]+b)
print(dp[h])
### BUGGY CODE ###

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

maxx = xlist[-1] if xlist[-1] > a else a
# dp[j][k][s]: x_1...x_jまでのなかからk枚選んで合計をsにする総数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0][0] = 1  # 0枚選んで合計を0にするのは1通り
for j in range(n + 1):
  for k in range(n + 1):
    for s in range(maxx * k + 1):
      if j >= 1 and s < xlist[j-1]:  # x_0は選ばないのと同じなので0のまま更新しない
        dp[j][k][s] = dp[j-1][k][s]
      elif j >= 1 and k >= 1 and s >= xlist[j-1]:
        dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-xlist[j-1]]

ans = 0
for k in range(1, n + 1):
  ans += dp[n][k][k*a]
print(ans)

### FIXED CODE ###

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

maxx = max(x)
maxx = max(maxx, a)
# dp[j][k][s] : j枚目までからk枚選んで合計をsにする場合の数
dp = [[[0 for _ in range(maxx * n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for j in range(n + 1):
    for k in range(j + 1):
        for s in range(maxx * k + 1):
            if j >= 1 and s < x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j - 1]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j - 1]]

ans = 0
for k in range(1, n + 1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def silnia(n):
    c = n
    s = 1
    while c > 1:
        s = s*c
        c = c-1
    return s

class N_po_K:
    def __init__(self, modulo = 10**9+7): 
        self.modulo = modulo 
        
    def dwumian(self, N, K):
        if N < K: 
            return 0
        return silnia(N)//silnia(K)//silnia(N-K)%self.modulo

def min_max_sums(): 
    N, K = wczytaj_liste()
    A = wczytaj_liste()
    A.sort()
    suma_min = 0 
    suma_max = 0
    dwumianator = N_po_K()
    for i in range(N):
        suma_min += dwumianator.dwumian(N-i-1, K-1)*A[i]
        suma_max += dwumianator.dwumian(N-i-1, K-1)*A[-i-1]
    print((suma_max - suma_min)%(10**9+7))

min_max_sums()

### FIXED CODE ###

def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 


class N_po_K:
    def __init__(self, maxN, modulo = 10**9+7): 
        self.modulo = modulo
        self.silnie = [1]
        for i in range(1, maxN + 1):
            self.silnie.append(self.silnie[i - 1] * i % self.modulo)
        
    def dwumian(self, N, K):
        if N < K: 
            return 0
        return self.silnie[N] * pow(self.silnie[K], self.modulo - 2, self.modulo)\
                              * pow(self.silnie[N-K], self.modulo - 2, self.modulo) % self.modulo

def min_max_sums(): 
    N, K = wczytaj_liste()
    A = wczytaj_liste()
    A.sort()
    suma_min = 0 
    suma_max = 0
    dwumianator = N_po_K(N)
    for i in range(N):
        suma_min += dwumianator.dwumian(N-i-1, K-1)*A[i]
        suma_max += dwumianator.dwumian(N-i-1, K-1)*A[-i-1]
    print((suma_max - suma_min)%(10**9+7))

min_max_sums()
### BUGGY CODE ###

n, k = map(int, input().split(' '))
a = [int(i) for i in input().split(' ')]

dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    for x in range(1, min(i, k) + 1):
        dp[i] = min(dp[i], abs(a[i - x] - a[i]) + dp[i - x])
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split(' '))
a = [int(i) for i in input().split(' ')]

dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
    for x in range(1, min(i, k) + 1):
        z = abs(a[i - x] - a[i]) + dp[i - x]
        if dp[i] > z:
            dp[i] = z
print(dp[-1])
### BUGGY CODE ###

h,w,m = map(int, input().split())
row = [0]*(h+1)
rn = [[] for _ in range(h+1)]
col = [0]*(w+1)
cn = [[] for _ in range(w+1)]
data = []
for _ in range(m):
  hd,wd = map(int, input().split())
  row[hd] += 1
  rn[hd].append(wd)
  col[wd] += 1
  cn[wd].append(hd)

cm = max(col)
rm = max(row)
ri = [x for x,y in enumerate(row) if y == rm]
ci = [x for x,y in enumerate(col) if y == cm]
ans = -1
for c in ci:
  for r in ri:
    if c not in rn[r]:
      ans = max(ans,cm+rm)
    else:
      ans = max(ans,cm+rm-1)
print(ans)

### FIXED CODE ###

h,w,m = map(int, input().split())
row = [0]*(h+1)
rn = [[] for _ in range(h+1)]
col = [0]*(w+1)
cn = [[] for _ in range(w+1)]
data = []
for _ in range(m):
  hd,wd = map(int, input().split())
  row[hd] += 1
  rn[hd].append(wd)
  col[wd] += 1
  cn[wd].append(hd)

cm = max(col)
rm = max(row)
ri = [x for x,y in enumerate(row) if y == rm]
ci = [x for x,y in enumerate(col) if y == cm]
for r in ri:
  rs = set(rn[r])
  for c in ci:
    if c not in rs:
      ans = cm+rm
      print(ans)
      exit()
ans = cm+rm-1
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

def q(d, c):
    if c == 1: 
        if d < 10: return str(d), 0
    if d >= 10: 
        lem, count = q(d // 10 + d % 10, c)
        return lem, count + c
    elif c % 2 == 0:
        lem, count = q(d * 2, c // 2)
        return lem, count + c // 2
    elif c % 2 == 1:
        lem, count = q(d * 2, c //2)
        return lem + str(d), count + c // 2

def solve():
    input = sys.stdin.readline
    M = int(input())
    N = ""
    count = 0
    dq = deque()

    for _ in range(M):
        d, c = map(int, input().split())
        lem, add = q(d, c)
        for i in range(len(lem)): 
            dq.append(lem[i])
        count += add
    
    digit = len(dq)
    for _ in range(digit - 1):
        #print(dq)
        a = int(dq.pop())
        a += int(dq.pop())
        if a >= 10:
            dq.append(str(a % 10 + a // 10))
            count += 2
        else: 
            dq.append(str(a))
            count += 1

    print(count)
    
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque

def q(d, c): #dは9以下、cは桁数
    digsum = d * c
    add = c - 1 + (digsum - 1) // 9
    rem = digsum - 9 * ((digsum - 1) // 9)
    return add, rem

def solve():
    input = sys.stdin.readline
    M = int(input())
    count = -1
    ans = 0
    for _ in range(M):
        d, c = map(int, input().split())
        add, rem = q(d, c)
        count += add
        ans += rem
        count += 1
        if ans > 9:
            ans -= 9
            count += 1

    print(count)
    
    return 0

if __name__ == "__main__":
    solve()