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

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

import heapq

def main():
    H, W, M = map(int, readline().split())
    m = map(int,read().split())
    hw = list(zip(m,m))

    row_bombers = [0] * (H+1)
    col_bombers = [0] * (W+1)

    for (h, w) in hw:
        row_bombers[h] += 1
        col_bombers[w] += 1

    row_max = max(row_bombers)
    col_max = max(col_bombers)

    max_rows = [i for i in range(H+1) if row_bombers[i] == row_max]
    max_cols = [i for i in range(W+1) if col_bombers[i] == col_max]

    ans = row_max + col_max
    
    num_empty_cells_in_kouho = len(max_rows) * len(max_cols)
    for (h, w) in hw:
        if h in max_rows and w in max_cols:
            num_empty_cells_in_kouho -= 1

    if num_empty_cells_in_kouho == 0:
        ans -= 1
    
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

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

import heapq

def main():
    H, W, M = map(int, readline().split())
    m = map(int,read().split())
    hw = list(zip(m,m))

    row_bombers = [0] * (H+1)
    col_bombers = [0] * (W+1)

    for (h, w) in hw:
        row_bombers[h] += 1
        col_bombers[w] += 1

    row_max = max(row_bombers)
    col_max = max(col_bombers)

    max_rows = [i for i in range(H+1) if row_bombers[i] == row_max]
    max_cols = [i for i in range(W+1) if col_bombers[i] == col_max]

    ans = row_max + col_max
    
    num_empty_cells_in_kouho = len(max_rows) * len(max_cols)
    for (h, w) in hw:
        if row_bombers[h] == row_max and col_bombers[w] == col_max:
            num_empty_cells_in_kouho -= 1

    if num_empty_cells_in_kouho == 0:
        ans -= 1
    
    print(ans)


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

n, k = map(int, input().split())
h = list(map(int, input().split()))
 
a = [0]*n
 
for i in range(1, n):
  b = [a[j] + abs(h[i]-h[j]) for j in range(max(0, i-k), i)]
  a[i] = min(b)
print(a[-1])


### FIXED CODE ###

n, k = map(int, input().split())
hs = list(map(int, input().split()))
 
dp = [0]*n
 
for i in range(1, n):
  first = max(0, i-k)
  dp[i] = min([d + abs(hs[i]-h) for d, h in zip(dp[first:i], hs[first:i])])
print(dp[-1])
### BUGGY CODE ###

s = input()
x, y = map(int, input().split())
a = 0
t = [[0], [0]]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
z = [x, y]
for k in range(2):
    tt = t[k]
    zk = z[k]
    p = sum(tt)
    if zk > p or zk < -p:
        flag = False
        break
    dp = [[False for _ in range(2 * p + 1)] for i in range(2)]
    i = 1
    if k == 0:
        dp[0][p + tt[0]] = True
    else:
        dp[0][p + tt[0]] = True
        dp[0][p - tt[0]] = True
    if len(tt) > 1:
        for tj in tt[1:]:
            for j in range(tj):
                dp[i][j] = dp[1 - i][j + tj]
            for j in range(tj, 2 * p + 1 - tj):
                dp[i][j] = dp[1 - i][j + tj] or dp[1 - i][j - tj]
            for j in range(2 * p + 1 - tj, 2 * p + 1):
                dp[i][j] = dp[1 - i][j - tj]
            i = 1 - i
    if dp[1 - len(tt) % 2][zk + p]:
        flag = True
    else:
        flag = False
        break
if flag:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import defaultdict

s = input()
x, y = map(int, input().split())
a = 0
t = [[0], []]
n = 0
for i in range(len(s)):
    if s[i] == 'F':
        t[n][-1] += 1
    else:
        n = 1 - n
        t[n].append(0)
flag = [False, False]
z = [x, y]
for k in range(2):
    tt = t[k]
    zk = z[k]
    if len(tt) == 0:
        if zk == 0:
            flag = True
            continue
        else:
            print(1, k)
            flag = False
            break
    p = sum(tt)
    dp = defaultdict(bool)
    i = 1
    if k == 0:
        dp[tt[0]] = True
    else:
        dp[tt[0]] = True
        dp[-tt[0]] = True
    if len(tt) > 1:
        for tj in tt[1:]:
            dp2 = defaultdict(bool)
            for xj in dp.keys():
                dp2[xj + tj] = True
                dp2[xj - tj] = True
            dp = dp2
    flag = dp[zk]
    if not flag:
        break
if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

n, k = map(int, input().split())
s=0
for i in range(k, n+2):
	s += (sum(range(n+2-i, n+2)) - sum(range(i+1)) +1 )%(10**9 +7)
print(s%(10**9 +7))

### FIXED CODE ###

n, k = map(int, input().split())
import numpy
res = numpy.cumsum(range(n+2))
s=0
for i in range(k, n+2):
	s += (res[n+1] - res[n+1-i] - res[i] +1)%(10**9 +7)
print(s%(10**9 +7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def print_ans(A, B):
    """Test Case
    >>> print_ans(2, 4)
    5
    >>> print_ans(123, 456)
    435
    """
    # if (B -A + 1) % 2 == 0:
    #     print(122 ^ 1)
    # else:
    #     print( B ^ 1)
    tmp = A
    for i in range(A + 1, B + 1):
        tmp = tmp ^ i
    print(tmp)

    

if __name__ == '__main__':
    A, B = map(int, input().rstrip().split())
    print_ans(A, B)


### FIXED CODE ###

import sys
input = sys.stdin.readline
def calc(x):
    if x == 0:
        return 0
    r = x % 4
    if r == 0:
        return x
    elif r == 1:
        return 1
    elif r == 2:
        return 1 ^ x
    else:
        return 0
def print_ans(A, B):
    """Test Case
    >>> print_ans(2, 4)
    5
    >>> print_ans(123, 456)
    435
    >>> print_ans(123456789012, 123456789012)
    123456789012
    """
    tmp = calc(A -1)
    tmp2 = calc(B)
    print(tmp ^ tmp2)

    

if __name__ == '__main__':
    A, B = map(int, input().rstrip().split())
    print_ans(A, B)
### BUGGY CODE ###

class BinaryTree:
    def __init__(self):
        self.root = None
    def b_insert(self,x):
        self.root = insert(self.root,x)
    def b_inorder(self):
        return inorder(self.root)
    def b_preorder(self):
        return preorder(self.root)
        
class Node:
    def __init__(self,x):
        self.data = x
        self.left = None
        self.right = None
            
def insert(node,x):
    if node is None:
        return Node(x)
    elif x == node.data:
        return node
    elif x < node.data:
        node.left = insert(node.left,x)
    else:
        node.right = insert(node.right,x)
    return node
def inorder(node):
    nodelist = []
    if node.left:
        nodelist += inorder(node.left)
    nodelist += [node.data]
    if node.right:
        nodelist += inorder(node.right)
    return nodelist
def preorder(node):
    nodelist = [node.data]
    if node.left:
        nodelist += preorder(node.left)
    if node.right:
        nodelist += preorder(node.right)
    return nodelist

length = int(input())
bfs = BinaryTree()
for l in range(length):
    temp = input()
    if temp[0] == 'i':
        command,num = (n for n in temp.split(" "))
        bfs.b_insert(int(num))
    else:
        count = 0
        print("",end=" ")
        print(*bfs.b_inorder())
        print("",end=" ")
        print(*bfs.b_preorder())

### FIXED CODE ###

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, x):
        node = self.Node(x)
        if self.root is None:
            self.root = node
        else:
            here = self.root
            #
            temp = None
            while here is not None:
                temp = here
                if x < here.node:
                    here = here.left
                elif x > here.node:
                    here = here.right
            if x < temp.node:
                temp.left = node
            elif x > temp.node:
                temp.right = node

    def inorder(self, answer, address = "root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        self.inorder(answer, address.left)
        answer.append(address.node)
        self.inorder(answer, address.right)

    def preorder(self, answer, address = "root"):
        if address is "root":
            address = self.root
        elif address is None:
            return
        answer.append(address.node)
        self.preorder(answer, address.left)
        self.preorder(answer, address.right)

    class Node:
        def __init__(self, x):
            self.node = x
            self.left = None
            self.right = None

query = int(input())
bt = BinarySearchTree()
for _ in range(query):
    command = input()
    if command[0] == "i":
        bt.insert(int(command.split(" ")[1]))
    else:
        a = []
        bt.inorder(a)
        print(" ", end = "")
        print(*a)
        a = []
        bt.preorder(a)
        print(" ", end = "")
        print(*a)
### BUGGY CODE ###

import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heapq.heappush(q, e)
    while q:
        minedge = heapq.heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heapq.heappush(q, [e[0]+d[v], e[1]])
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, N, E)

    ans = A[N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, E):
    inf = float('inf')
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    heapq.heapify(q)
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, E)

    ans = A[N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


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

def main():
    from collections import Counter

    s = str(input())
    num = ""
    li = []
    f = 0
    mi = 0
    li_append = li.append

    cm = {}
    for i in range(1,2*(10 ** 5)):
        cm[i] = i * (i - 1) // 2
    cm[0] = 0



    for i in range(1, len(s) + 1):
        num = s[-i] + num
        li_append(int(num) % 2019)
        if num[0] == "0":
            f += 1
        else:
            mi += cm[f+1]
            f = 0

    co = Counter(li)
    val = [i for i in co.values() if i > 1]
    ans_1 = 0

    for x in val:
        ans_1 += cm[x]
    ans2 = 0
    if 0 in co:
        ans2 = co[0]
    print(ans_1 + ans2 - mi)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

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

a, b, c, d, e, f = list(map(int, input().split(' ')))


rate = 0
water = 0
suger = 0
for i in range(30 + 1):
    for j in range(30 + 1):
        for k in range(100 + 1):
            for l in range(100 + 1):
                w = 100 * a * i + 100 * b * j
                s = c * k + d * l
                if w + s <= 0:
                    break
                temp = w + s
                r = (s * 100) / temp
                if temp <= f and (a * i + b * j) * e >= s:
                    if rate <= r:
                        water = w
                        suger = s 
                        rate = r
print(water + suger, suger)


### FIXED CODE ###

a, b, c, d, e, f = list(map(int, input().split(' ')))


rate = 0
water = 0
suger = 0

al = f // (a * 100)
bl = f // (b * 100)
for i in range(al + 1):
    for j in range(bl + 1):
        for k in range(100 + 1):
            for l in range(100 + 1):
                w = 100 * a * i + 100 * b * j
                s = c * k + d * l
                if w + s <= 0:
                    break
                temp = w + s
                r = (s * 100) / temp
                if temp <= f and (a * i + b * j) * e >= s:
                    if rate <= r:
                        water = w
                        suger = s 
                        rate = r
print(water + suger, suger)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    dp = [[[0] * 4 for _ in range(W + 1)] for _ in range(H + 1)]
    for r in range(H):
        for c in range(W):
            cell = dp[r][c]
            up = dp[r - 1][c]
            left = dp[r][c - 1]

            for k in range(4):
                cell[0] = max(cell[0], up[k])
                cell[k] = max(cell[k], left[k])

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-2][-2])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    pdp = [[0] * 4 for _ in range(W)]
    for r in range(H):
        dp = [[0] * 4 for _ in range(W)]
        left = [0] * 4
        for c in range(W):
            cell = dp[c]

            for k in range(4):
                cell[k] = left[k]

            up = max(pdp[c])
            if cell[0] < up:
                cell[0] = up

            for k in range(2, -1, -1):
                cell[k + 1] = max(
                    cell[k + 1],
                    cell[k] + G[r][c])
            left = cell
        pdp = dp

    # for k in range(4):
    #     for row in range(H):
    #         for col in range(W):
    #             print(dp[row][col][k], end=' ')
    #         print()
    #     print()

    # print(*G, sep='\n')

    ans = max(dp[-1])
    print(ans)


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

import numpy as np
import functools
import operator

n,k= map(int,input().split())
a = list(map(int,input().split()))
target = a[0:k]
# print(target)
p = functools.reduce(operator.mul, target)
# print(p)
for i in range(n-k):
    ans = (p // a[i]) * a[i+k]
    # print(ans)
    if ans > p:
        print("Yes")
    else:
        print("No")
    p = ans


### FIXED CODE ###

import numpy as np

n,k= map(int,input().split())
a = list(map(int,input().split()))
target = a[0:k]
p = sum(target)
for i in range(n-k):
    ans = p - a[i] + a[i+k]
    # print(ans)
    if ans > p:
        print("Yes")
    else:
        print("No")
    p = ans
### BUGGY CODE ###

from collections import deque

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

v = [[] for i in range(N + 1)]
vin = [0 for i in range(N + 1)]

parent = [0 for i in range(N + 1)]
# visited = [False for i in range(N + 1)]

for i in range(N + M - 1):
    A, B = map(int, input().split())
    v[A].append(B)
    vin[B] += 1

Q = deque()
for i in range(1, N + 1):
    if vin[i] == 0:
        Q.append((i, 0))
        break

while len(Q) != 0:
    now, pa = Q.popleft()
    parent[now] = pa
    # if visited[now]:
    #     continue
    for i in v[now]:
        Q.append((i, now))
    # visited[now] = True

for i in range(1, N + 1):
    print(parent[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

N, M = map(int, input().split())
BtoA = [[] for i in range(N + 1)]


for i in range(N - 1 + M):
    A, B = map(int, input().split())
    BtoA[B].append(A)

memo = {}
def depth(b):
    if b in memo:
        return memo[b]
    
    res = 0
    for a in BtoA[b]:
        res = max(res, depth(a) + 1)

    memo[b] = res
    return res

for i in range(1, N + 1):
    ans = 0
    for a in BtoA[i]:
        if depth(a) + 1 == depth(i):
            ans = a
            break
    print(ans)
### BUGGY CODE ###

from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
count=0
b=Counter(a)
count_list=[0]*(10**6)
for i in a:
  if b[i]==1:
    if count_list[i-1]==0:
      count+=1
      j=1
      while i*j<=10**6:
        count_list[i*j-1]+=1
        j+=1
  else:
    j=2
    while i*j<=10**6:
      count_list[i*j-1]+=1
      j+=1
print(count)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
a_max=a[-1]
count=0
b=Counter(a)
count_list=[0]*(a_max)
for i in a:
  if b[i]==1:
    if count_list[i-1]==0:
      count+=1
      j=1
      while i*j<=a_max:
        count_list[i*j-1]+=1
        j+=1
  else:
    j=2
    while i*j<=a_max:
      count_list[i*j-1]+=1
      j+=1
print(count)
### BUGGY CODE ###

def gcd(x_y):
    tmp = list(map(int, x_y.split()))
    x = tmp[0]
    y = tmp[1]

    xcd = set([ n for n in range(1, x+1) if  x % n == 0])  # xの約数
    ycd = set([ n for n in range(1, y+1) if  y % n == 0])  # yの約数
    cd = list(xcd & ycd)  # ｘとyの公約数
    print(max(cd))  # ｘとyの最大公約数

x_y = input()
gcd(x_y)


### FIXED CODE ###

def gcd(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp
    while y > 0:
        r = x % y
        x = y
        y = r

    return print(x)

x_y = input()
tmp = list(map(int, x_y.split()))
x = tmp[0]
y = tmp[1]
gcd(x, y)
### BUGGY CODE ###

import bisect
N,M=map(int, input().split() )
A=list(map(int, input().split() ))
B=[0]*M
C=[0]*M
for i in range(M):
  B[i],C[i]=map(int, input().split() )
A.sort()
summ=sum(A)

for i in range(M):
  p=bisect.bisect_left(A,C[i])
  q=min(p,B[i])
  A= [C[i]]*q+ A[q:]
  A.sort()
  
print(sum(A))

### FIXED CODE ###

from collections import Counter

N,M = map(int, input().split() )
A   = list(map(int, input().split() ))
B   = [0]*M
C   = [0]*M
Cou = Counter(A)

for i in range(M):
  B[i],C[i]  = map(int, input().split() )
  Cou[C[i]] += B[i]
  
#print(Cou)  
ans=0
cnt=0
S=sorted(Cou,reverse=True)
#print(S)
for num in S:
  kosuu = min(Cou[num],N-cnt)
  cnt += kosuu
  ans += num*kosuu
  
print(ans)
### BUGGY CODE ###

N, A, B = map(int, input().split())
round_count = 0

med = N / 2 + 0.5

while(True):
    if abs(A - B) % 2 == 0:
        if A > B:
            A = A - 1
            B = B + 1

            if A < 1:
                A = 1
            elif B > N:
                B = N
        else:
            A = A + 1
            B = B - 1

            if A > N:
                A = N
            elif B < 1:
                B = 1
    else:
        Max = max([A, B])
        Min = min([A, B])
        if (Max + Min) / 2 > med:
            A = A + 1
            B = B + 1

            if A > N:
                A = N
            elif B > N:
                B = N
        else:
            A = A - 1
            B = B - 1

            if A < 1:
                A = 1
            elif B < 1:
                B = 1

    round_count = round_count + 1

    if A == B:
        break

print(round_count)

### FIXED CODE ###

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

med = N / 2 + 0.5
Sub = B - A

if (Sub) % 2 == 0:
    round_count = Sub // 2
else:
    round_count = min(A - 1, N - B) + 1 + (Sub - 1) // 2
            
print(round_count)
### BUGGY CODE ###

import fractions
N,M=map(int, input().split())
A = [int(a) for a in input().split()]
A2 = [a//2 for a in A]

lcm = A2[0]
for i in range(1, N):
    lcm = lcm * A2[i] // fractions.gcd(lcm, A2[i])

B = sum([1 for a in A if lcm%a==0])
if B>0:
    print(0)
else:
    print((M//lcm+1)//2)

### FIXED CODE ###

import sys
import fractions
N,M=map(int, input().split())
A = [int(a) for a in input().split()]
A2 = [a>>1 for a in A]

lcm = A2[0]
for i in range(1, N):
    lcm = lcm * A2[i] // fractions.gcd(lcm, A2[i])
    if lcm>M:
        print(0)
        sys.exit()
    
B = sum([1 for a in A if lcm%a==0])
if B>0:
    print(0)
else:
    print((M//lcm+1)//2)
### BUGGY CODE ###

import numpy as np
N,K = list(map(int,input().split()))
A = input()
A = list(A)
A = list(map(int,A))
l = [0]
s = []
for i in range(N-1):
    if A[i] != A[i+1]:
        l.append(i+1)
        s.append(l[len(l)-1]-l[len(l)-2])
l.append(N)
s.append(l[len(l)-1]-l[len(l)-2])
a = 0
s = np.array(s)
if A[0]==0:
    for i in range(len(s)):
        if i%2==0:
            a = max(a,sum(s[i:i+2*K]))
        else :
            a = max(a,sum(s[i:i+2*K+1]))
else:
    for i in range(len(s)):
        if i%2==0:
            a = max(a,sum(s[i:i+2*K+1]))
        else:
            a = max(a,sum(s[i:i+2*K]))
print(a)

### FIXED CODE ###

N,K = list(map(int,input().split()))
A = input()
A = list(A)
A = list(map(int,A))
l = [0]
s = []

for i in range(N-1):
    if A[i] != A[i+1]:
        l.append(i+1)
        s.append(l[len(l)-1]-l[len(l)-2])
l.append(N)
s.append(l[len(l)-1]-l[len(l)-2])
a = 0
right = 0
left = 0
g = 0
su = 0
if A[0] == 0:
    for i in range(len(s)):
        su +=s[right]
        if right%2==0:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==0:
                  g -=1
              left +=1
        a = max(a,su)
else:
    for i in range(len(s)):
        su +=s[right]
        if right%2==1:
            g += 1
        right +=1
        if g<=K:
            a = max(a,su)
        else:
            while g>K:
              su -= s[left]
              if left%2==1:
                  g -=1
              left +=1
        a = max(a,su)

print(a)
### BUGGY CODE ###

import copy

arrays = []
n,m,q = 0,0,0

def main():
    global n, m, q
    global arrays
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(q)]
    ans = 0
    dfs([], 1)
    for array in arrays:
        tmp = 0
        for i in range(q):
            if array[abcd[i][1]-1] - array[abcd[i][0]-1] == abcd[i][2]:
                tmp += abcd[i][3]
        ans = max(ans, tmp)
    print(ans)

def dfs(stack, i):
    stack.append(i)
    if len(stack) == n:
        arrays.append(copy.deepcopy(stack))
        if i < m:
            stack.pop()
            dfs(copy.deepcopy(stack), i + 1)
        return
    dfs(copy.deepcopy(stack), i)
    if i < m:
        stack.pop()
        dfs(copy.deepcopy(stack), i + 1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import copy

arrays = []
n,m,q = 0,0,0

def main():
    global n, m, q
    global arrays
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(q)]
    ans = 0
    dfs([], 1)
    for array in arrays:
        tmp = 0
        for i in range(q):
            if array[abcd[i][1]-1] - array[abcd[i][0]-1] == abcd[i][2]:
                tmp += abcd[i][3]
        ans = max(ans, tmp)
    print(ans)

def dfs(stack, i):
    stack.append(i)
    if len(stack) == n:
        arrays.append(copy.deepcopy(stack))
        if i < m:
            stack.pop()
            dfs(copy.deepcopy(stack), i + 1)
        return
    dfs(copy.deepcopy(stack), i)
    if i < m:
        stack.pop()
        dfs(copy.deepcopy(stack), i + 1)

if __name__ == '__main__':
    main()