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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 0
N = read_a_int()
A = []
for a in read().split():
    A.append(int(a))
    n = max(n, len(bin(int(a))) - 2)


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += ((2**i) * n_1) % MOD
        else:
            ret += ((2**i) * (n_1_max - n_1)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import itertools

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)
     
    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)
     
    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s

n,m = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for _ in range(n)]

lr.sort(key=lambda x: x[1]-x[0])

#print(lr)

omiyage = RangeUpdate(m+1)
index = 0
for d in range(1,m+1):
    while(index < n and lr[index][1] - lr[index][0] < d):
        omiyage.add(lr[index][0]+1, lr[index][1]+1, 1)
        index+=1
    ans = 0
    pos = 0
    while(pos <= m):
        ans += omiyage.sum(pos+1,pos+1)
        pos += d
    ans += n-index
    print(ans)
    
    






        





### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline #文字列入力のときは注意

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.base = [0]* (n+1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        self.base[i] += x
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
    def get(self, i):
        return self.base[i]

class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)
     
    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)
     
    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
               self.p.sum(s) - self.q.sum(s) * s

#    def get(self, s):
#        return self.p.sum(s+1) + self.q.sum(s+1) * (s+1) - \
#               self.p.sum(s) - self.q.sum(s) * s
    def get(self, s):
        return self.p.get(s+1) + self.q.get(s+1) * (s+1) + self.q.sum(s) 



n,m = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for _ in range(n)]

lr.sort(key=lambda x: x[1]-x[0])

#print(lr)

omiyage = RangeUpdate(m+1)
index = 0
for d in range(1,m+1):
    while(index < n and lr[index][1] - lr[index][0] < d):
        omiyage.add(lr[index][0]+1, lr[index][1]+1, 1)
        index+=1
    ans = 0
    pos = 0
    while(pos <= m):
        ans += omiyage.get(pos+1)
        pos += d
    ans += n-index
    print(ans)
### BUGGY CODE ###

import math
x = int(input())
b = 0

def calc(b, b5):
    a = (x+b5)**0.2

    if a.real.is_integer():
        print(int(a), b)
        exit()

while True:
    b5 = b ** 5
    calc(b, b5)
    calc(-b, -b5)
    b += 1


### FIXED CODE ###

import math
x = int(input())
b = 0

"""
def calc(b, b5):
    a = (x+b5)**0.2

    if a.real.is_integer():
        print(int(a), b)
        exit()

while True:
    b5 = b ** 5
    calc(b, b5)
    if x-b5 >= 0:
        calc(-b, -b5)
    b += 1
    """

for i in range(-120,120):
    for j in range(-120,120):
        if i**5 - j**5 == x:
            print(i, j)
            exit()
### BUGGY CODE ###

def resolve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    for i in range(N):
        P[i] -= 1

    ans = -1e18
    for i in range(N):
        n = P[i]
        score = C[n]
        t = [score]
        while n != i:
            n = P[n]
            score += C[n]
            t.append(score)

        total = t[-1]
        l = len(t)
        for i in range(min(K, l)):
            temp_score = t[i]
            if total > 0 and K > l:
                e = int((K-(i+1))/l)
                temp_score += total*e
            ans = max(ans, temp_score)

    print(ans)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))
    for i in range(N):
        P[i] -= 1

    ans = -1e18
    for i in range(N):
        n = P[i]
        score = C[n]
        t = [score]
        while n != i:
            n = P[n]
            score += C[n]
            t.append(score)

        total = t[-1]
        l = len(t)
        for i in range(min(K, l)):
            temp_score = t[i]
            if total > 0 and K > l:
                e = int((K-(i+1))/l)
                temp_score += total*e
            ans = max(ans, temp_score)

    print(ans)


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

k = int(input())
def dfs(n):
    if n==0:
        return 2
    elif n==1:
        return 1
    else:
        return dfs(n-1)+dfs(n-2)
print(dfs(k))

### FIXED CODE ###

n = int(input())
def lucas(x):
    a = 2
    b = 1
    for i in range(x):
        a,b = b,a+b
    return a
print(lucas(n))
### BUGGY CODE ###

import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        im = judge(m - 1, N, A)
        ip = judge(m + 1, N, A)
        if i == M:
            X = m
            break
        if im == M:
            X = m - 1
            break
        if ip == M:
            X = m + 1
            break
        if i > M:
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            if im > M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())


### FIXED CODE ###

import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())
### BUGGY CODE ###

S=int(input())
N=input()
a=S
for i in range(S):
    if i==0:
        if a>N[1:].count("E"):
            a=N[1:].count("E")
    elif i==len(N)-1:
        if a>N[:len(N)].count("W"):
            a=N[:len(N)].count("W")
    else:
        if a>N[:i].count("W")+N[i+1:].count("E"):
            a=N[:i].count("W")+N[i+1:].count("E")
print(a)

### FIXED CODE ###

from collections import deque
N=int(input())
S=input()
w=[0]
e=[0]
a=0
b=0
c=N
for i in range(len(S)-1):
    if S[i]=="W":
        a+=1   
    w.append(a)
    if S[-(i+1)]=="E":
        b+=1
    e.append(b)
for i in range(N):
    d=w[i]+e[-(i+1)]
    if d<c:
        c=d
print(c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(20000*20000)

S = str(input())
ans = set()

def dfs(i, j):
    if int(S[i:j+1])%2019 == 0:
        ans.add((i, j))
        return
    if j == len(S)-1:
        return

    dfs(i+1, j+1)
    dfs(i, j+1)

if len(S) < 4:
    print(0)

else:
    dfs(0, 3)
    print(len(ans))

### FIXED CODE ###

s=input()
n=len(s)
mod=2019
d=0
p=1
ml=[0]*mod
for i in range(1,n+1):
  k=int(s[-i])
  d+=p*k
  d%=mod
  ml[d]+=1
  p*=10
  p%=mod
ans=0
for i in ml:
  ans+=i*(i-1)//2
print(ans+ml[0])
### BUGGY CODE ###

from functools import lru_cache
import collections
import copy

@lru_cache(maxsize=2*10**5)
def f(p):
    c=copy.deepcopy(b)
    c[x]-=1
    d=c.values()
    e=0
    for y in d:
        e+=y*(y-1)
    return e//2


n=int(input())
a=list(map(int,input().split()))
b=collections.Counter(a)

for x in a:
    print(f(x))

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int,input().split()))
b=collections.Counter(a)
e=0
for x in b.values():
    e+=x*(x-1)
for x in a:
    t=b[x]
    p=e-t*(t-1)+(t-1)*(t-2)
    print(p//2)
### BUGGY CODE ###

from itertools import combinations

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

count = 0
for a, b, c in combinations(ls, 3):
    if a < b + c and b < c + a and c < a + b:
        count += 1

print(count)

### FIXED CODE ###

# from itertools import combinations
from bisect import bisect_left

n = int(input())
ls = list(map(int, input().split()))
ls.sort()

count = 0

# for a, b, c in combinations(ls, 3):
#     if a < b + c and b < c + a and c < a + b:
#         count += 1

# for j in range(n - 1, 1, -1):
#     last = ls[j]
#     for a, b in combinations(ls[:j], 2):
#         if a + b > last:
#             count += 1

for i in range(n - 1, 1, -1):
    for j in range(i - 1, 0, -1):
        idx = bisect_left(ls[:j], ls[i] - ls[j] + 1)
        if idx < j:
            count += j - idx

print(count)
### BUGGY CODE ###

from itertools import product
D, G = map(int, input().split())
npcs = []
for i in range(D):
    n, c = map(int, input().split())
    p = (i + 1) * 100
    npcs.append((n, p, c))
npcs.sort(key=lambda x: x[0])
result = sum(map(lambda x: x[0], npcs))
for ns in product(*[range(n + 1) for n, p, c in npcs[:-1]]):
    sump = 0
    sumn = 0
    for i, n in enumerate(ns):
        maxn, p, c = npcs[i]
        sump += n * p
        if n == maxn:
            sump += c
        sumn += n
    if sump >= G:
        if sumn < result:
            result = sumn
    else:
        s = G - sump
        lmaxn, lp, lc = npcs[-1]
        if s <= lmaxn * lp + lc:
            if s > (lmaxn - 1) * lp:
                sumn += lmaxn
            else:
                sumn += s // lp
                if s % lp != 0:
                    sumn += 1
            if sumn < result:
                result = sumn
print(result)

### FIXED CODE ###

import functools
D, G = map(int, input().split())
G = G // 100
sumn = 0
ns = [0] * (D + 1)
cs = [0] * (D + 1)
for i in range(1, D + 1):
    n, c = map(int, input().split())
    ns[i] = n
    cs[i] = c // 100
    sumn += n

minn = [0] * (D + 1)
for i in range(1, D + 1):
    minn[i] = min(ns[1:i+1])

@functools.lru_cache(maxsize=None)
def f(i, rn):
    if i == 1:
        if ns[1] < rn:
            return -1
        p = rn
        if ns[1] == rn:
            p += cs[1]
        return p
    if rn < minn[i]:
        p = 0
        for j in range(i, 0, -1):
            n = min((ns[j], rn))
            p += j * n
            if n == rn:
                break
            rn -= n
        return p
    maxp = 0
    for n in range(min((ns[i], rn)) + 1):
        p = i * n
        if n == ns[i]:
            p += cs[i]
        np = f(i - 1, rn - n)
        if np >= 0:
            p += np
            if maxp < p:
                maxp = p
    return maxp

mn = 1
mx = sumn
while mn < mx:
    x = mn + ((mx - mn) // 2)
    if G <= f(D, x):
        mx = x
    else:
        mn = x + 1
print(mn)
### BUGGY CODE ###

import math
A,B,N =map(int,input().split())
ans =0
for x in range(1,N+1):
  num = math.floor(A*x/B) - A * math.floor(x/B)
  if num > ans:
    ans = num

print(ans)

### FIXED CODE ###

import math

A,B,N = map(int,input().split())
if B>N:
  print( math.floor(A*N/B) - A * math.floor(N/B))
  exit()
print( math.floor(A*(B-1)/B) - A * math.floor((B-1)/B))
### BUGGY CODE ###

N,M,K = map(int, input().split())
MOD = 998244353

fact = [1]
rfact = [1]
for i in range(1, N+1):
    fact.append(fact[i-1]*i%MOD)
    rfact.append(pow(fact[i], MOD-2, MOD))
 
def cmb(n, m):
    return fact[n]*rfact[m]*rfact[n-m]%MOD

answer = 0
for i in range(K+1):
    answer += M*cmb(N-1,i)*(M-1)**(N-1-i)*1**i
print(answer%MOD)

### FIXED CODE ###

N,M,K = map(int, input().split())
MOD = 998244353

fact = [1]
rfact = [1]
for i in range(1, N+1):
    fact.append(fact[i-1]*i%MOD)
    rfact.append(pow(fact[i], MOD-2, MOD))
 
def cmb(n, m):
    return fact[n]*rfact[m]*rfact[n-m]%MOD

answer = 0
for i in range(K+1):
    answer += (M*cmb(N-1,i)*pow(M-1,N-1-i,MOD))%MOD
print(answer%MOD)
### BUGGY CODE ###

import math

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

max_num=max(a)
middle_num=math.ceil(max_num/2)
middle_num_up=middle_num
middle_num_down=middle_num

if n>2:
    for i in range(n):
        if middle_num_up in a:
            ans=middle_num_up
            break
        if middle_num_down in a:
            ans=middle_num_down
        else:
            middle_num_up+=1
            middle_num_down-=1
else:
    ans=min(a)

print("{} {}".format(max_num,ans))

### FIXED CODE ###

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

max_num=max(a)
middle_num=max_num/2
num=0

for i in range(n):
    if a[i]> middle_num:
        num=i
        break

if middle_num-a[num-1]<=-middle_num+a[num]:
    print("{} {}".format(max_num,a[num-1]))
else:
    print("{} {}".format(max_num,a[num]))
### BUGGY CODE ###

n = int(input())
a = [list(map(lambda s: int(s) - 1, input().split())) for _ in range(n)]

def f():
    day = 0
    ptrs = [0] * n
    players = set(range(n))

    while players:
        visited = set()
        removals = set()
        for i in players:
            if i in visited:
                continue
            
            x = a[i][ptrs[i]] # iの次候補
            if x in visited:
                continue

            y = a[x][ptrs[x]] # xの次候補
            if i == y:
                ptrs[i] += 1
                ptrs[x] += 1
                visited.add(i)
                visited.add(x)
                if ptrs[i] == n - 1:
                    removals.add(i)
                if ptrs[x] == n - 1:
                    removals.add(x)

        # すべて未訪問の場合
        if len(visited) == 0:
            return -1
        players -= removals
        day += 1
    
    return day



print(f())

### FIXED CODE ###

import collections

n = int(input())
a = [collections.deque(int(s) - 1 for s in input().split()) for _ in range(n)]

day = 0
players = set(range(n))
while any(v for v in a):
    nxt_players = set()
    for player in players:
        if len(a[player]) == 0 or player in nxt_players:
            continue
        
        other = a[player][0]
        if len(a[other]) == 0 or other in nxt_players:
            continue
        
        if player == a[other][0]:
            a[player].popleft()
            a[other].popleft()
            nxt_players.add(player)
            nxt_players.add(other)

    if nxt_players:
        day += 1
        players = nxt_players
    else:
        print(-1)
        exit()

print(day)
### BUGGY CODE ###

L,R = map(int,input().split())
a = []
for i in range(L,min(R,L+2019*2)+1):
    a.append(i)
ans = 10**10
b = len(a)
for i in range(b):
    for j in range(b):
        if i<=j:
            break
        ans=min(ans,(a[i]*a[j])%2019)
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
a = [i for i in range(L,min(L+2019,R)+1)]
b = len(a)
ans = 10**10
for i in range(b):
    for j in range(b):
        if i==j:
            break
        ans = min(ans,a[i]*a[j]%2019)
print(ans)
### BUGGY CODE ###

s = input()
lst = list(s)

cnt = 0
madaikeru = True
while madaikeru:
    if len(s) < 3:
        madaikeru = False
    else:
        for i in range(len(s)-2):
            if lst[i]=='A' and lst[i+1]=='B' and lst[i+2]=='C':
                lst[i] = 'B'
                lst[i+1] = 'C'
                lst[i+2] = 'A'
                cnt += 1
                break
            if i == len(s)-3:
                madaikeru = False

print(cnt)

### FIXED CODE ###

s = input()
s = s.replace('BC', 'D')
lst = list(s)

acount = 0
ans = 0
for i in range(len(s)):
    if s[i] == 'A':
        acount += 1
    elif s[i] == 'D':
        ans += acount
    else:
        acount = 0

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

N, Q = map(int, input().split())
S = input()
l = [list(map(int, input().split())) for _ in range(Q)]
for i in range(Q):
	print(S[l[i][0] - 1: l[i][1]].count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
count = [0]*N  # count[i] は i 番目まで S[:i+1] の解
for i in range(1, N):
    count[i] = count[i-1]
    if S[i-1: i+1] == "AC":
        count[i] += 1
for _ in range(Q):
    l,r = map(int, input().split())
    print(count[r-1] - count[l-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(X: int):
    dp = [[False]*(X+1) for _ in range(7)]
    price = [100,101,102,103,104,105]

    for i in range(7):
        dp[i][0] = True

    ## i番目まででjを払えるか
    for i in range(6):
        for j in range(X+1):
            if j >= price[i]:
                for k in range(1,j//price[i]+1):
                    dp[i+1][j] |= dp[i][j] or dp[i][j-k*price[i]]
            else:
                dp[i+1][j] = dp[i][j]

    if dp[6][X]:
        print(1)
    else:
        print(0)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(X: int):
    dp = [[-1]*(X+1) for _ in range(7)]
    price = [100,101,102,103,104,105]
    m = [10**5]*6

    for i in range(7):
        dp[i][0] = 10**5

    ## i番目まででjを払えるか
    for i in range(6):
        for j in range(X+1):
            if dp[i][j]>=0:
                dp[i+1][j] = m[i]
            elif j < price[i] or dp[i+1][j-price[i]]<=0:
                dp[i+1][j] = -1
            else:
                dp[i+1][j] = dp[i+1][j-price[i]]-1

    if dp[6][X]>=0:
        print(1)
    else:
        print(0)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    solve(X)

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

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)


### FIXED CODE ###

from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    if ans < cnt:
        ans = cnt
print(ans)