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

import heapq
import sys
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])
    while q:
        min_dist, v_from = heapq.heappop(q)
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to_info in v_tos:
            v_to, cost = v_to_info
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, [dist[v_to], v_to])
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [[xs, ys, 0], [xt, yt, 0]]
    for _ in range(N):
        br.append(list(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.buffer.readline


def dijkstra(adj, start):
    # adj: [[to, cost] * vertices], 0th index must be empty
    dist = [float('inf')] * len(adj)
    dist[start] = 0
    q = []
    heapq.heappush(q, (0, start))
    while q:
        min_dist, v_from = heapq.heappop(q)
        # if v_from == 2:
        #    return dist
        if min_dist > dist[v_from]:
            continue
        v_tos = adj[v_from]
        for v_to, cost in v_tos:
            if min_dist + cost < dist[v_to]:
                dist[v_to] = min_dist + cost
                heapq.heappush(q, (dist[v_to], v_to))
    return dist


def main():
    xs, ys, xt, yt = map(int, input().split())
    N = int(input())
    br = [(xs, ys, 0), (xt, yt, 0)]
    for _ in range(N):
        br.append(tuple(map(int, input().split())))

    adj = [[] for _ in range(N+3)]
    for i in range(N+2):
        for j in range(i+1, N+2):
            dij = max(((br[i][0] - br[j][0])**2 + (br[i][1] - br[j][1])**2) ** (1/2) - (br[i][2] + br[j][2]), 0)
            adj[i+1].append([j+1, dij])
            adj[j+1].append([i+1, dij])

    print(dijkstra(adj, 1)[2])


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

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in G[now] :
        if col[i] == -1 :
            col[i] = (col[now] + 1)%2
            stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = mod0 + mod1 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()
else :
    mods = mod1 + mod0 + mod2
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.pop(0)
        else :
            ans[i] = mods.pop()

print(*ans)


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
G = [[] for _ in range(N)]
for i in range(N-1) :
    a, b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

col = [-1]*N
col[0] = 0
stack = deque([0])
while stack :
    now = stack.pop()
    for i in G[now] :
        if col[i] == -1 :
            col[i] = (col[now] + 1)%2
            stack.append(i)

mod0 = [x for x in range(1, N+1) if x%3 == 0]
mod1 = [x for x in range(1, N+1) if x%3 == 1]
mod2 = [x for x in range(1, N+1) if x%3 == 2]

ans = [0 for _ in range(N)]
if sum(col) <= N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 1 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
elif sum(col) >= 2*N//3 :
    mods = deque(mod0 + mod1 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()
else :
    mods = deque(mod1 + mod0 + mod2)
    for i in range(N) :
        if col[i] == 0 :
            ans[i] = mods.popleft()
        else :
            ans[i] = mods.pop()

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

n = int(input())
T = [int(input()) for _ in range(n)]

main_t = max(T)
cur = main_t
flag = True
while 1:
	for t in T:
		if cur%t != 0:
			flag = False
			break
	if flag:
		ans = cur
		break
	cur += main_t
	flag = True
	# print(cur)

print(ans)

### FIXED CODE ###

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

n = int(input())
T = [int(input()) for _ in range(n)]

ans = 1
for t in T:
	ans = ans*t//gcd(ans,t)
print(ans)
### BUGGY CODE ###


from bisect import insort_left

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

if not N-1:
  A[0] //= 2 ** M
		
else:
  while M:
	  a = A.pop(N-1)
	
	  while a >= A[-1] and M:
		  a //= 2
		  M -= 1
		
	  insort_left(A, a)
	
print(sum(A))

### FIXED CODE ###

from heapq import heappush, heappop, heapify

def main():
  N, M = map(int, input().split())
  A = list(map(int, input().split()))

  if N == 1: A[0] = A[0] // 2 ** M
  else:
    for i in range(N): A[i] *= -1

    heapify(A)

    for i in range(M):
      a = heappop(A)
      heappush(A, -(-a//2))

  print(-sum(A))  
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

r1,c1,r2,c2 = map(int, input().split())

def nCr_mod_p(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 7  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

sum22 = nCr_mod_p(r2+1+c2+1,r2+1,p) - 1
sum21 = nCr_mod_p(r2+1+c1,r2+1,p) - 1
sum12 = nCr_mod_p(r1+c2+1,c2+1,p) - 1
sum11 = nCr_mod_p(r1+c1,c1,p) - 1

ans = sum22 - sum21 - sum12 + sum11
ans %= p

print(ans)


### FIXED CODE ###

r1,c1,r2,c2 = map(int, input().split())

def nCr_mod_p(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 2*10 ** 6 + 10  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

sum22 = nCr_mod_p(r2+1+c2+1,r2+1,p) - 1
sum21 = nCr_mod_p(r2+1+c1,r2+1,p) - 1
sum12 = nCr_mod_p(r1+c2+1,c2+1,p) - 1
sum11 = nCr_mod_p(r1+c1,c1,p) - 1

ans = sum22 - sum21 - sum12 + sum11
ans %= p

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

s=list(input())
N=len(s)
n=0
ans=0
while n<N-2:
    if s[n:n+3]==["A","B","C"]:
        ans+=1
        s[n:n+3]=["B","C","A"]
        n-=2
    n+=1
print(ans)

### FIXED CODE ###

s=list(input())
S=[]
n=0
while n+1<len(s):
    if s[n:n+2]==["B","C"]:
        S.append("D")
        n+=1
    else:
        S.append(s[n])
    n+=1
a=0
ans=0
for i in range(len(S)):
    if S[i]=="D":
        ans+=a
    elif S[i]=="A":
        a+=1
    else:
        a=0
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-09-27 01:01:29 +0900
# LastModified: 2020-09-27 01:12:14 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
from collections import Counter


def main():
    N = int(input())
    S = input()
    S = [s for s in S]
    ans = 0
    for i in range(N):
        if i == 0:
            obj = S[1:]
            ans = obj.count('E')
            continue
        elif i == N-1:
            obj = S[:i]
            cnt = obj.count('W')
        else:
            obj_1 = S[:i]
            obj_2 = S[i+1:]
            cnt = obj_1.count('W') + obj_2.count('E')
        if ans > cnt:
            ans = cnt
    print(ans)

    


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C_fix
# CreatedDate:  2020-09-27 01:13:48 +0900
# LastModified: 2020-09-27 01:29:07 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    N = int(input())
    S = input()
    RW_cnt = S.count("W")
    RE_cnt = S.count("E")
    LW_cnt = 0
    LE_cnt = 0
    if S[0] == "W":
        RW_cnt -= 1
        LW_cnt = 1
    else:
        RE_cnt -= 1
        LE_cnt = 1
    ans = RE_cnt
#    print("RW_cnt, RE_cnt, LW_cnt, LE_cnt")
    for i in range(1, N):
        if i == N-1:
            cnt = LW_cnt
        else:
            cnt = LW_cnt + RE_cnt
        if cnt < ans:
            ans = cnt
        if S[i] == "E":
            LE_cnt += 1
            RE_cnt -= 1
        else:
            LW_cnt += 1
            RW_cnt -= 1
#        print(RW_cnt, RE_cnt, LW_cnt, LE_cnt)
    print(ans)


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

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    X = input().decode()
    X = list(X)

    def popcount(x):
        # 2bitごとの組に分け、立っているビット数を2bitで表現する
        x = x - ((x >> 1) & 0x5555555555555555)

        # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
        x = x + (x >> 8)  # 16bitごと
        x = x + (x >> 16)  # 32bitごと
        x = x + (x >> 32)  # 64bitごと = 全部の合計
        return x & 0x0000007f

    # X = ['']*N
    # for i in range(N):
    #     X[i] = str(random.randint(0, 1))
    # print("".join(X))
    C = X.count("1")

    dp = [0]*N
    dp[0] = 0
    for i in range(1, N):
        k = i % popcount(i)
        dp[i] = 1 + dp[k]

    # def solve(n, d):

    for i in range(N):
        if X[i] == "0":
            X[i] = '1'
            print(dp[int((''.join(X)), 2) % (C+1)] + 1)
            #tmp = dp[int((''.join(X)), 2) % (C+1)] + 1
            X[i] = '0'
        else:
            if C == 1:
                print(0)
                continue
            X[i] = '0'
            print(dp[int((''.join(X)), 2) % (C-1)] + 1)
            #tmp = dp[int((''.join(X)), 2) % (C-1)] + 1
            X[i] = '1'


main()
# print(dp)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    X = input().decode()
    K = int(X, 2)
    X = list(X)

    def popcount(x):
        # 2bitごとの組に分け、立っているビット数を2bitで表現する
        x = x - ((x >> 1) & 0x5555555555555555)

        # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
        x = x + (x >> 8)  # 16bitごと
        x = x + (x >> 16)  # 32bitごと
        x = x + (x >> 32)  # 64bitごと = 全部の合計
        return x & 0x0000007f

    # X = ['']*N
    # for i in range(N):
    #     X[i] = str(random.randint(0, 1))
    # print("".join(X))
    C = X.count("1")
    dpL = [0]*N
    dpR = [0]*N
    tmp = 1
    dpL[0] = 1 % (C+1)
    L = K % (C+1)

    if C == 1:
        R = 0
    else:
        R = K % (C-1)
        dpR[0] = 1 % (C-1)

    for i in range(1, N):
        dpL[i] = dpL[i-1]*2 % (C+1)
        if C > 1:
            dpR[i] = dpR[i-1]*2 % (C-1)

    dp = [0]*N
    dp[0] = 0
    for i in range(1, N):
        k = i % popcount(i)
        dp[i] = 1 + dp[k]

    # def solve(n, d):

    for i in range(N):
        if X[i] == "0":
            print(dp[(L + dpL[N-i-1]) % (C+1)] + 1)
        else:
            if C == 1:
                print(0)
                continue
            X[i] = '0'
            print(dp[(R - dpR[N-i-1]) % (C-1)] + 1)
            #tmp = dp[int((''.join(X)), 2) % (C-1)] + 1
            X[i] = '1'


main()
# print(dp)
### BUGGY CODE ###

a = input()
n = int(input())
b = 1
for i in range(n):
    q = input()
    if q == "1":
        b = (b+1)%2
    else:
        q,f,c = q.split()
        if int(f)%2 == b:
            a = c+a
        else:
            a = a+c
if b == 0:
    a = a[::-1]
print(a)

### FIXED CODE ###

a = input()
n = int(input())
rev = False
front = []
back = []
q = [input() for i in range(n)]
for i in q:
    if i == "1":
        rev = not rev
    else:
        i,f,c = i.split()
        if rev == False:
            if f == "1":
                front.append(c)
            else:
                back.append(c)
        else:
            if f == "1":
                back.append(c)
            else:
                front.append(c)
if rev == False:
    print("".join(list(reversed(front))+[a]+back))
else:
    print("".join(list(reversed(back))+[a[::-1]]+front))
### BUGGY CODE ###

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

for n in range(0, N):
    print(A.count(n + 1))

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = [int(n) for n in input().split()]

d = defaultdict(int)
for i in A:
    d[i-1] += 1
for n in range(N):
    print(d[n])
### BUGGY CODE ###

def clear_maze(sx, sy, gx, gy, maze):

    INF = 100000000

    distance = [[INF for i in range(W)] for j in range(H)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sy][sx] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < W and 0 <= ny and ny < H and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (nx, ny))
                    distance[ny][nx] = distance[y][x] + 1


        return distance[gy][gx]

    return bfs()

H,W = (int(x) for x in input().split())
maze = ['']*H
max_distance = 0
for i in range(H):
  maze[i] = list(input())
  
dic = {}
for i in range(H*W):
  dic[i] = [i % W,i//W,0]
  
for i in range(H*W):
  sx,sy = dic[i][0],dic[i][1]
  if maze[sy][sx] == '#':
    continue
  for j in range(H*W):
    gx,gy = dic[j][0],dic[j][1]
    if (sx == gx and sy == gy) or maze[gy][gx] == '#' or dic[j][2] == 1:
        continue
    tmp_s = maze[sy][sx]
    tmp_g = maze[gy][gx]
    maze[sy][sx] = 'S'
    maze[gy][gx] = 'G'
    max_distance = max(max_distance,clear_maze(sx, sy, gx, gy, maze))
    maze[sy][sx] = tmp_s
    maze[gy][gx] = tmp_g
    dic[i][2] = 1
        
print(max_distance)
    

    

### FIXED CODE ###

from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
def bfs(maze,h,w,sx,sy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    m = 0                   
    for l in maze:
      li = [i for i in l if i != '#' and i < 1000000]
      if len(li) > 0:
        m = max(m,max(li))
    return m
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    copymaze = copy.deepcopy(maze)
    res = bfs(copymaze,H,W,sj,si)
    max_dist = max(max_dist,res)
print(max_dist)
### BUGGY CODE ###

# DP
N, M = map(int, input().split())
broken = [int(input()) for _ in range(M)]

MOD = 10**9+7
dp = [0 for i in range(N+2)]
dp[N] = 1

for i in reversed(range(N)):
    if i in broken:
        continue
    dp[i] = dp[i+1] + dp[i+2]
    dp[i] %= MOD

print(dp[0])


### FIXED CODE ###

N, B = map(int, input().split())
ana = []
dp = [0] * (N+2)

for i in range(B):
    ana.append(int(input()))

mod = 1000000007

dp[N] = 1
for i in reversed(range(N)):
    if len(ana) >= 1 and i == ana[-1]:
        dp[i] = 0
        if len(ana) != 0:
            ana.pop(-1)
        continue
    dp[i] = dp[i + 1] + dp[i + 2]
print(dp[0] % mod)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    c = input()
    if c == "deleteFirst":
        a.pop(0)
    elif c == "deleteLast":
        a.pop()
    else:
        c, v = c.split()
        v = int(v)
        if c == "insert":
            a.insert(0, v)
        elif v in a:
            a.remove(v)
print(" ".join(map(str, a)))


### FIXED CODE ###

from collections import deque
n = int(input())
a = deque()
for i in range(n):
    c = input()
    if c == "deleteFirst":
        a.popleft()
    elif c == "deleteLast":
        a.pop()
    else:
        c, v = c.split()
        if c == "insert":
            a.appendleft(v)
        else:
            try:
                a.remove(v)
            except:
                pass
print(" ".join(a))
### BUGGY CODE ###

R,G,B,N = map(int, input().split())
ans = 0
for i in range(0,1+N//R):
    #print(i,1 + (N-i*R)//G)
    for j in range(0,1 + (N-i*R)//G):
        k = (N-i*R-j*G)//B
        if N == R*i + G*j + B*k:
            ans += 1

print(ans)

### FIXED CODE ###

R,G,B,N = map(int, input().split())
ans = 0
for i in range(0,1+N//R):
    #print(i,1 + (N-i*R)//G)
    for j in range(0,1 + (N-i*R)//G):
        k = (N-i*R-j*G)//B
        if N == R*i + G*j + B*k:
            ans += 1

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

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

ans = 0

for i in range(n):
    tmp = p[:i+1]
    if min(tmp) >= p[i]:
        ans += 1

print(ans)

### FIXED CODE ###

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

ans = 1
tmp_min = p[0]

for i in range(1, n):
    if tmp_min >= p[i]:
        tmp_min = p[i]
        ans += 1

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

import sys
input=sys.stdin.readline
from collections import defaultdict
h, w, d = map(int, input().split())

I = defaultdict(list)
D = defaultdict(list)
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        I[x%d].append(x)
        D[x%d].append((x, i, j))
q = int(input())

for key in D.keys():
    I[key].sort()
    D[key].sort()

for i in range(q):
    a, b = map(int, input().split())
    u = I[a%d]
    v = D[a%d]
    l = u.index(a)
    r = u.index(b)
    tmp = v[l:r+1]
    _, s, t = tmp[0]
    ans = 0
    for _,  u, v in tmp[1:]:
        ans += abs(u-s)+abs(v-t)
        s, t = u, v
    print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()

for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dp = [0]*(h*w+1)
for i in range(h*w+1):
    if d < i:
        dp[i] = dp[i-d] + abs(p[i][0]-p[i-d][0])+abs(p[i][1]-p[i-d][1])

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = dp[b]-dp[a]
    print(ans)
### BUGGY CODE ###

def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      array[s+1:] = array[s]
      #for i in range(s+1,0):#以降の項を全て同じ値に
        #array[i] = array[s]
        
  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])

array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
    array = next_array(array)#次の配列へ
    
print(max_scr)

### FIXED CODE ###

def next_array(array):#辞書式に次の配列を与える関数
  s = -1
  for x in array[::-1]:
    if x < M:
      break
    else:
      s -= 1
    #Mより小さい最後の項を取得
  
  if s >= -N:
    array[s] += 1#その項を１増やす
    if s < -1:
      for i in range(s+1,0):#以降の項を全て同じ値に
        array[i] = array[s]

  return array
 
def score(array, rules):#点数計算
  scr = 0
  for rule in rules:
    if (array[rule[1]-1] - array[rule[0]-1] == rule[2]):
      scr += rule[3]
      
  return scr
 
# input
N, M, Q = map(int, input().split())
rules = []
 
for i in range(Q):
  a, b, c, d = map(int, input().split())
  rules.append([a, b, c, d])
  
array = [1] * N
max_scr = 0
 
while True:
  max_scr = max(max_scr, score(array,rules)) 
  if array[0] == M:#全探索完了
    break 
  array = next_array(array)#次の配列へ
    
print(max_scr)
### BUGGY CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    input = readline
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = [0] * H
    Wlist = [0] * W
    hw = []

    for _ in range(M):
        h, w = map(int, input().split())
        Hlist[h-1] += 1
        Wlist[w-1] += 1
        hw.append([h, w])


    hmax = [i for i, x in enumerate(Hlist) if x == max(Hlist)]
    wmax = [i for i, x in enumerate(Wlist) if x == max(Wlist)]
    hmaxset = set(hmax)
    wmaxset = set(wmax)

    flag = False
    count = 0
    for hh in hw:
        h = hh[0] - 1
        w = hh[1] - 1
        if h in hmaxset and w in wmaxset:
            count += 1
    if count != len(hmax) * len(wmax):
        flag = True

    if flag:
        print(Hlist[hmax[0]] + Wlist[wmax[0]])
    else:
        print(Hlist[hmax[0]] + Wlist[wmax[0]] - 1)





if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    input = readline
    mod = 10 ** 9 + 7
    H, W, M = map(int, input().split())
    Hlist = collections.defaultdict(int)
    Wlist = collections.defaultdict(int)
    hw = []

    for _ in range(M):
        h, w = map(int, input().split())
        Hlist[h-1] += 1
        Wlist[w-1] += 1
        hw.append([h, w])

    #hmax = [i for i, x in enumerate(Hlist) if x == max(Hlist)]
    #wmax = [i for i, x in enumerate(Wlist) if x == max(Wlist)]

    Hlist = sorted(Hlist.items(), key=lambda x: x[1], reverse=True)
    Wlist = sorted(Wlist.items(), key=lambda x: x[1], reverse=True)

    hmaxset = set()
    wmaxset = set()

    maxH = Hlist[0][1]
    for k, v in Hlist:
        if v != maxH:
            break
        else:
            hmaxset.add(k)

    maxW = Wlist[0][1]
    for k, v in Wlist:
        if v != maxW:
            break
        else:
            wmaxset.add(k)


    flag = False
    count = 0
    for hh in hw:
        h = hh[0] - 1
        w = hh[1] - 1
        if h in hmaxset and w in wmaxset:
            count += 1

    lenhmax = len(hmaxset)
    lenwmax = len(wmaxset)

    if count != lenhmax * lenwmax:
        flag = True

    if flag:
        print(maxH + maxW)
    else:
        print(maxH + maxW - 1)





if __name__ == '__main__':
    solve()