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

import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp = np.empty((3**N, N), np.int64)  # 建設、人 -> コスト
    dp[0] = np.minimum(np.abs(X), np.abs(Y)) * P
    size = np.empty(3**N, np.int64)
    size[0] = 0
    for n in range(N):
        B = 3**n
        DX = np.abs(X - X[n]) * P
        DY = np.abs(Y - Y[n]) * P
        dp[B:2 * B] = np.minimum(dp[:B], DX)
        dp[2 * B:3 * B] = np.minimum(dp[:B], DY)
        size[B:2 * B] = size[:B] + 1
        size[2 * B:3 * B] = size[:B] + 1
    ans = np.full(N + 1, 10**18, np.int64)
    for s in range(3**N):
        n = size[s]
        ans[n] = min(ans[n], dp[s].sum())
    return ans

N = int(readline())
XYP = np.array(read().split(), np.int64)

ans = main(XYP)
print('\n'.join(map(str, ans.tolist())))


### FIXED CODE ###

import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], ), cache=True)
def main(XYP):
    X, Y, P = XYP[::3], XYP[1::3], XYP[2::3]
    N = len(X)
    dp_X = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト
    dp_X[0] = np.abs(X) * P
    for n in range(N):
        B = 1 << n
        dp_X[B:2 * B] = np.minimum(dp_X[:B], np.abs(X - X[n]) * P)

    dp_Y = np.empty((1 << N, N), np.int64)  # 建設、人 -> Xコスト
    dp_Y[0] = np.abs(Y) * P
    for n in range(N):
        B = 1 << n
        dp_Y[B:2 * B] = np.minimum(dp_Y[:B], np.abs(Y - Y[n]) * P)

    popcount = np.zeros(1 << N, np.int64)
    for n in range(N):
        popcount[1 << n:1 << n + 1] = popcount[:1 << n] + 1

    INF = 10**18
    ans = np.full(N + 1, INF, np.int64)
    for s in range(1 << N):
        size = popcount[s]
        t = s
        while True:
            u = s ^ t
            cost = (np.minimum(dp_X[t], dp_Y[u])).sum()
            ans[size] = min(ans[size], cost)
            if t == 0:
                break
            t = (t - 1) & s
    return ans

N = int(readline())
XYP = np.array(read().split(), np.int64)

ans = main(XYP)
print('\n'.join(map(str, ans.tolist())))
### BUGGY CODE ###

n = 50001
is_prime = [True for i in range(n)]
is_prime[0] = is_prime[1] = False
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = False
        j += i
    i += 1

cnt_pair = [0 for i in range(n)]
for i in range(n//2):
    if is_prime[i]:
        for j in range(i, n - i):
           if is_prime[j]:
               cnt_pair[i + j] += 1

while True:
    n = int(input())
    if n == 0:
        break
    print(cnt_pair[n])



### FIXED CODE ###

n = 50001
is_prime = [i for i in range(n)]
is_prime[0] = is_prime[1] = 0
i = 2
while i**2 <= n:
    j = i*2
    while j < n:
        is_prime[j] = 0
        j += i
    i += 1

prime_set  = set(is_prime)
prime_set.remove(0)
prime_list = sorted(list(prime_set))

while True:
    cnt = 0
    n = int(input())
    if n == 0:
        break
    for i in prime_list:
        if i > n//2:
            break
        if n - i in prime_set:
            cnt += 1
    print(cnt)
### BUGGY CODE ###

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
F=sorted(map(int,input().split()))[::-1]

left,right=-1,10**12
while left + 1 < right:
    mid = (left + right)//2
    if sum([max(0,a-mid//f) for a,f in zip(A,F)])>K:
        left = mid
    else:
        right = mid
print(right)

### FIXED CODE ###

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
F=sorted(map(int,input().split()))[::-1]

left,right=-1,10**12
while left + 1 < right:
    mid = (left + right)//2
    if sum([max(0,a-mid//f) for a,f in zip(A,F)])>K:
        left = mid
    else:
        right = mid
print(right)
### BUGGY CODE ###

from heapq import heappop, heappush
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
F = [int(i) for i in input().split()]
A.sort()
F.sort(reverse=True)
H = []
for i in range(N):
    heappush(H,(-A[i]*F[i],F[i]))

while K>0:
    K -= 1
    x,y = heappop(H)
    x = min(0,x+y)
    heappush(H,(x,y))
print(-H[0][0])

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
f = list(map(int,input().split()))
a.sort()
f.sort(reverse=True)


ng = -1
ok = 10**12
while ok-ng > 1:
    mid = (ok+ng)//2
    cnt = 0

    for i,e in enumerate(a):    
        cnt += max(0,e-mid//f[i])
    if cnt <= k:
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import numpy as np

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


MOD = 1000000007
numbers = np.array(S).astype(np.int64)
numbers = np.sort(numbers)


#dp = np.zeros((N+1, X+1), dtype=int)
dp = np.arange(X+1)
dp_n = []
i = 0
for n  in numbers:
    dp_n = np.zeros((X+1), dtype=np.int64)
    dp_n += [dp[x % n] for x in range(X+1)]
    dp_n = dp_n % MOD
    dp_n += dp * i % MOD
    dp_n = dp_n % MOD
    dp = dp_n
    i += 1

print(int(dp_n[X]) % MOD)


### FIXED CODE ###

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

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

from itertools import permutations

h,w = map(int,input().split())
nec = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "#":
            nec.append([i,j])

com = [1 for i in range(w-1)]+[0 for i in range(h-1)]
ans = False
alr = set()
for p in permutations(com):
    if p in alr:
        continue
    else:
        alr.add(p)
    # print(p)
    st = [0, 0]
    root = [[0, 0]]
    for c in p:
        if c == 1:
            nex = [st[0],st[1]+1]
            st = nex
            root.append(nex)
        else:
            nex = [st[0]+1,st[1]]
            st = nex
            root.append(nex)

    flags = [False for i in range(len(nec))]
    for i in range(len(nec)):
        if nec[i] in root:
            flags[i] = True
    # print(flags)
    ans = all(flags) or ans

if ans:
    print("Possible")
else:
    print("Impossible")


### FIXED CODE ###

from itertools import permutations

h,w = map(int,input().split())
nec = []
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "#":
            nec.append([i,j])

if len(nec) == h+w-1:
    print("Possible")
else:
    print("Impossible")
### BUGGY CODE ###

N = int(input())
l = list(map(int, input().split()))
set_l = set(l)

dictionary = {ll: l.count(ll)for ll in set_l}

for n in range(N):
  cnt = 0
  for k, v in dictionary.items():
    if k==l[n]:
      v -=1
    cnt += v*(v-1)/2
  print(int(cnt))

### FIXED CODE ###

from collections import Counter

N = int(input())
l = list(map(int, input().split()))
set_l = set(l)

dictionary = Counter(l)
ll_dict = {}

cnt = 0
for k, v in dictionary.items():
  cnt += v*(v-1)//2

for n in range(N):
  print(cnt-(dictionary[l[n]]-1))
### BUGGY CODE ###

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

for i in range(len(a)):
    ans*= a[i]

if ans<1000000000000000001:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

n=input()
a = list(map(int, input().split()))
ans=1
az=a.count(0)

if az>0:
    print(0)
else:
    for i in range(len(a)):
        ans*= a[i]
    
        if ans>=1000000000000000001:
            ans=-1
            break
    print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
su=sum(a)
c=[]#[abs(sum(a[:i+1])-su/2)*2 for i in range(n)]

for i in range(n):
  c+=[abs(sum(a[:i+1])-su/2)*2]
  if sum(a[:i+1])-su/2 >0 or sum(a[:i+1])-su/2==0:
    break
print(int(min(c)))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
import itertools
b = list(itertools.accumulate(a))
for i in range(n):
  b[i] = abs(2*b[i]-b[-1])
print(min(b))
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra,floyd_warshall
N,X,Y = map(int, input().split())
D = np.zeros((N,N))
for i in range(N-1):
  D[i][i+1]=1
  D[i+1][i]=1
D[X-1][Y-1]=1
D[Y-1][X-1]=1
A = floyd_warshall(D)
for k in range(1,N): print (np.sum(A==k)//2)


### FIXED CODE ###

from collections import defaultdict as dd
N,X,Y = map(int, input().split())
D = dd(int)
for i in range(1,N):
  for j in range(i+1,N+1):
    D[min(abs(i-j),abs(X-i)+abs(Y-j)+1,abs(Y-i)+abs(X-j)+1)] += 1 
for k in range(1,N):
  print (D[k])
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    C = list(input())
    cnt = 0
    red_cnt = 0
    B = sorted(C)
    for c in B:
        if c == 'R':
            red_cnt += 1
        else:
            break
    for i in range(N):
        if C[i] == 'W':
            for j in range(red_cnt, N):
                if C[j] == 'R':
                    C[i] = 'R'
                    C[j] = 'W'
                    cnt += 1
                    red_cnt = j+1
    print(cnt)

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    C = list(input())
    cnt = 0
    red_cnt = 0
    for c in C:
        if c == 'R':
            red_cnt += 1

    for i in range(red_cnt):
        if C[i] == 'W':
            for j in range(red_cnt, N):
                if C[j] == 'R':
                    C[i] = 'R'
                    C[j] = 'W'
                    cnt += 1
                    red_cnt = j+1
    print(cnt)
### BUGGY CODE ###

import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():
    R, C, K = map(int, input().split())
    A = [[0]*C for _ in range(R)]
    for i in range(K):
        r, c, v = map(int, input().split())
        r, c = r-1, c-1
        A[r][c] = v

    dp = [[[0]*4 for i in range(C+1)] for j in range(R+1)]
    for i in range(R):
        for j in range(C):
            for k  in reversed(range(3)):
                dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]+A[i][j])
            for k in range(4):
                dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])
                dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
    #print(dp)
    print(max(dp[R-1][C-1]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#import io, os
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

import sys
input = sys.stdin.buffer.readline

def main():
    R, C, K = map(int, input().split())
    A = [[0]*C for _ in range(R)]
    for i in range(K):
        r, c, v = map(int, input().split())
        r, c = r-1, c-1
        A[r][c] = v

    dp0 = [[0]*(C+1) for i in range(R+1)]
    dp1 = [[0]*(C+1) for i in range(R+1)]
    dp2 = [[0]*(C+1) for i in range(R+1)]
    dp3 = [[0]*(C+1) for i in range(R+1)]
    for i in range(R):
        for j in range(C):
            dp3[i][j] = max(dp3[i][j], dp2[i][j]+A[i][j])
            dp2[i][j] = max(dp2[i][j], dp1[i][j]+A[i][j])
            dp1[i][j] = max(dp1[i][j], dp0[i][j]+A[i][j])

            dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])
            dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
            dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
            dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])

            dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp1[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp2[i][j])
            dp0[i+1][j] = max(dp0[i+1][j], dp3[i][j])
    #print(dp)
    print(max([dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1]]))

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

from collections import deque
N, X, Y = map(int, input().split())

K = [0 for _ in range(N)]
INF = 10 ** 9
def bfs(n):
    d = deque()
    d.append(n)
    reached = [INF for _ in range(N)]
    reached[n] = 0
    dx = [-1, 1]
    while d:
        x = d.popleft()
        for i in range(2):
            nx = x + dx[i]
            if nx < 0 or nx > N - 1 or reached[nx] != INF:
                continue
            d.append(nx)
            reached[nx] =reached[x] + 1
        if x == X-1 and reached[Y-1] == INF:
            reached[Y-1] = reached[x] + 1
            d.append(Y-1)
        if x == Y-1 and reached[X-1] == INF:
            reached[X-1] = reached[x] + 1
            d.append(X-1)
    for i in range(N):
        K[reached[i]] += 1            

for i in range(N):
    bfs(i)

for i in range(1, N):
    print(K[i]//2)

### FIXED CODE ###

from collections import deque
N, X, Y = map(int, input().split())

K = [0 for _ in range(N)]
INF = 10 ** 9
def bfs(n):
    d = deque()
    d.append(n)
    reached = [INF for _ in range(N)]
    reached[n] = 0
    dx = [-1, 1]
    while d:
        x = d.popleft()
        for i in range(2):
            nx = x + dx[i]
            if nx < 0 or nx > N - 1 or reached[nx] != INF:
                continue
            d.append(nx)
            reached[nx] =reached[x] + 1
        if x == X-1 and reached[Y-1] == INF:
            reached[Y-1] = reached[x] + 1
            d.append(Y-1)
        if x == Y-1 and reached[X-1] == INF:
            reached[X-1] = reached[x] + 1
            d.append(X-1)
    for i in range(N):
        K[reached[i]] += 1            

for i in range(N):
    bfs(i)

for i in range(1, N):
    print(K[i]//2)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7
n, m = map(int, input().split())

pow_ = [0] * 31
divisor = 2
power = 0
while m % divisor == 0:
    m //= divisor
    power += 1
if power > 0:
    pow_[power] += 1

divisor = 3
while m > 1:
    power = 0
    while m % divisor == 0:
        m //= divisor
        power += 1
    if power > 0:
        pow_[power] += 1
    divisor += 2

# print(pow_)

ans = 1
t = 1
d = 1
for power, cnt in enumerate(pow_[1:], 1):
    # 1 <= power <= 30
    t = t * (n - 1 + power) % mod
    d = d * pow(power, mod - 2, mod) % mod
    # print(power, cnt, ans, t, d)
    for _ in range(cnt):
        ans = ans * t * d % mod
print(ans)


### FIXED CODE ###

MOD = 10 ** 9 + 7


def prime_factorization(n):
    i = 2
    res = []
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        i += 1
    if n > 1:
        res.append(1)
    return res


def comb(a, b):
    b = min(b, a - b)
    if b < 0:
        return 0
    elif b == 0:
        return 1
    elif b == 1:
        return a
    else:
        return (a % MOD) * pow(b, MOD - 2, MOD) % MOD * comb(a - 1, b - 1) % MOD


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

ans = 1
for power in prime_factorization(M):
    ans *= comb(N - 1 + power, power)
    ans %= MOD

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

import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, sys.stdin.readline().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, d = map(int, sys.stdin.readline().split())
    l, r = l - 1, r - 1
    G[l].append((r, d))
    G[r].append((l, -d))

R = [None] * N


def dfs(u):
    global R, G
    for w, d in G[u]:
        if not R[w]:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


for i in range(N):
    if not R[i]:
        R[i] = 0
        if not dfs(i):
            print('No')
            exit()

print('Yes')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
N, M = map(int, sys.stdin.readline().split())
G = [[] for i in range(N)]
for i in range(M):
    l, r, q = map(int, sys.stdin.readline().split())
    G[l - 1].append((r - 1, q))
    G[r - 1].append((l - 1, -q))

R = [None] * N


def dfs(u):
    global R, G
    for w, d in G[u]:
        if R[w] is None:
            R[w] = R[u] + d
            if not dfs(w):
                return False
        else:
            if R[w] != R[u] + d:
                return False
    return True


flag = True
for i in range(N):
    if R[i] is None:
        R[i] = 0
        flag &= dfs(i)

if flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

score = 0
for i in range(N):
    B = A
    keep = B.pop(0)
    n = gcd_list(B)
    if n > score:
        score = n
    A.append(keep)


print(score)

### FIXED CODE ###

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

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

L = [0 for i in range(N+1)]
R = [0 for j in range(N+1)]

for i in range(N):
    L[i+1] = fractions.gcd(L[i],A[i])
    R[N-1-i] = fractions.gcd(R[N-i],A[N-i-1])

M = 0
for i in range(N):
    M = max(M,fractions.gcd(L[i],R[i+1]))

print(M)
### BUGGY CODE ###

def main():
	n,p = map(int,input().split())
	s = input()
	num = 0
	s1 = [0]*(n+1)
	ans = 0
	if p == 2 or p == 5:
		for i in range(len(s)):
			if int(s[i])%p == 0:
				ans += i+1	
		print(ans)
		return
	ans = 0
	arr = [0]*p
	s = s[::-1]
	z = 1
	for i in range(n):
		s1[i+1] = s1[i] + int(s[i])*z
		z *=10 %p
		s1[i+1] %=p
		arr[s1[i]] += 1
	arr[s1[n]]+=1
	#print(s1)
	for i in range(p):
		ans += arr[i] * (arr[i] - 1) // 2
	print(ans)

if __name__ == '__main__':
	main()


### FIXED CODE ###

def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s=s*10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

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

N,Q = map(int, input().split())
chi = [set([i]) for i in range(N)]
par = [set([i]) for i in range(N)]


for n in range(N-1):
    a,b = map(int, input().split())
    chi[a-1].add(b-1)
    par[b-1].add(a-1)
    f = par[a-1]
    for i in f:
        chi[i] = chi[i] | chi[a-1]
        par[a-1] = par[a-1] | par[i]
            
cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   for i in chi[p-1]:
       cnt[i] += x

for n in range(N):
    print(cnt[n], end=" ")

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
        
N,Q = (int(i) for i in input().split())
A = [[] for _ in range(N)]

for _ in range(N-1):
    a,b = (int(i) for i in input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)

cnt = [0]*N   
for q in range(Q):
   p,x = (int(i) for i in input().split())
   cnt[p-1] += x

st = deque([(0,-1)])
while st:
    n,par = st.popleft()
    val = cnt[n]   
    for node in A[n]:
        if node == par:
            continue
        else:
            cnt[node] += val
            st.append([node,n])

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

import fractions

PRIME = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))

if n == 1:
  print(1)
else:
  lcm = a[0]
  for i in range(1, n):
    lcm = lcm * a[i] // int(fractions.gcd(lcm, a[i]))
  
  ans = 0
  for i in range(n):
    ans = (ans + lcm // a[i]) % PRIME
  
  print(ans)

### FIXED CODE ###

import fractions
 
PRIME = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
 
if n == 1:
  print(1)
else:
  lcm = a[0]
  for i in range(1, n):
    lcm = lcm * a[i] // int(fractions.gcd(lcm, a[i]))
  
  ans = 0
  for i in range(n):
    ans += lcm // a[i]
  
  print(ans % PRIME)
### BUGGY CODE ###

import numpy as np


N = int(input())
L = list(map(int,input().split()))
L.sort()
L = np.array(L)
ans = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        length = L[i]+L[j]
        tmp = L[j+1:]
        tmp = tmp[tmp<length]
        ans += len(tmp)
                 

print(ans)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int,input().split()))
L.sort()

ans = 0

for i in range(N):
    for j in range(i+1,N):
        ans += bisect.bisect_left(L,L[i]+L[j]) - (j+1)
print(ans)
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * H
w = [0] * W
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    item_h -= 1
    item_w -= 1
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

h_max = max(h)
w_max = max(w)
ans = h_max + w_max
index_num_h = [n for n, v in enumerate(h) if v == h_max]
index_num_w = [n for n, v in enumerate(w) if v == w_max]

cnt = -1
for h_i in index_num_h:
    for w_i in index_num_w:
        d = [h_i, w_i]
        if d not in item_list:
            cnt = 0
            print(ans)
            exit()

if cnt == -1:
    ans -= 1

print(ans)


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


H, W, M = MI()
h = [0] * H
w = [0] * W
item_list = [[0, 0] for _ in range(M)]

for i in range(M):
    item_h, item_w = MI()
    item_h -= 1
    item_w -= 1
    h[item_h] += 1
    w[item_w] += 1
    item_list[i][0] = item_h
    item_list[i][1] = item_w

h_max = max(h)
w_max = max(w)
h_cnt = h.count(h_max)
w_cnt = w.count(w_max)
ans = h_max + w_max

cnt = 0
for item in item_list:
    if h[item[0]] == h_max and w[item[1]] == w_max:
        cnt += 1

x = h_cnt * w_cnt
if cnt == x:
    ans -= 1

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

counter = 0

def merge(L, R, left, right):
    A = [i for i in range(0,right-left)]
    L.append(float('inf'))
    R.append(float('inf'))

    i,j=(0,0)
    global counter
    for n in range(0,right-left):
        counter = counter+1
        if L[i]<=R[j]:
            A[n]=L[i]
            i=i+1
        else:
            A[n]=R[j]
            j=j+1
    return A

def mergeSort(A, left, right):
    if left+1 < right:
        mid = int((left+right)/2)
        L = mergeSort(A[left:mid],0,mid-left)
        R = mergeSort(A[mid:right],0,right-mid)
        A = merge(L, R, left, right)
    return A

n = int(input())
l = list(map(int,input().split()))
ll = mergeSort(l,0,n)
print(*ll)
print(counter)

### FIXED CODE ###

counter = 0

def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]
    #print(L)
    #print(R)
    L.append(float('inf'))
    R.append(float('inf'))
    i=j=0
    global counter
    for k in range(left,right):
        counter = counter+1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A, left, right):
    if left+1<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

n = int(input())
l = list(map(int,input().split()))
mergeSort(l,0,n)
print(*l)
print(counter)