Problem:
 Score : 300 points    Problem Statement Given are positive integers N , M , Q , and Q quadruples of integers ( a_i , b_i , c_i , d_i ).  Consider a sequence A satisfying the following conditions:   A is a sequence of N positive integers.  1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M .   Let us define a score of this sequence as follows:   The score is the sum of d_i over all indices i such that A_{b_i} - A_{a_i} = c_i . (If there is no such i , the score is 0 .)   Find the maximum possible score of A .      Constraints  All values in input are integers.  2 ≤ N ≤ 10  1 \leq M \leq 10  1 \leq Q \leq 50  1 \leq a_i < b_i \leq N ( i = 1, 2, ..., Q )  0 \leq c_i \leq M - 1 ( i = 1, 2, ..., Q )  (a_i, b_i, c_i) \neq (a_j, b_j, c_j) (where i \neq j )  1 \leq d_i \leq 10^5 ( i = 1, 2, ..., Q )         Input Input is given from Standard Input in the following format:  N  M  Q  a_1  b_1  c_1  d_1  :  a_Q  b_Q  c_Q  d_Q       Output Print the maximum possible score of A .        Sample Input 1 3 4 3
1 3 3 100
1 2 2 10
2 3 2 10      Sample Output 1 110  When A = \{1, 3, 4\} , its score is 110 . Under these conditions, no sequence has a score greater than 110 , so the answer is 110 .       Sample Input 2 4 6 10
2 4 1 86568
1 4 0 90629
2 3 0 90310
3 4 1 29211
3 4 3 78537
3 4 2 8580
1 2 1 96263
1 4 2 2156
1 2 0 94325
1 4 3 94328      Sample Output 2 357500       Sample Input 3 10 10 1
1 10 9 1      Sample Output 3 1

Solution (Python):
n, m, q = map(int, input().split())
ans = 0
a, b, c, d = [None]*q, [None]*q, [None]*q, [None]*q
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

def dfs(A):
    if len(A) == n+1:
        now = 0
        for i in range(q):
            if A[b[i]]-A[a[i]] == c[i]:
                now += d[i]
        global ans
        ans = max(ans, now)
        return
    A.append(A[-1])
    while A[-1] <= m:
        dfs(A[:])
        A[-1] += 1

if __name__ == "__main__":
    dfs([1])
    print(ans)

Solution (Python):
import itertools
n,m,q = (int(x) for x in input().split())
l = []
a = [1,2,3,4,5,6,7,8,9,10]
b = []
c = []
d = []


for i in range(q):
    l.append([])
    l[i]=list(map(int, input().split()))
    
for i in itertools.combinations_with_replacement(a[:m], r=n):
        b.append(i)        
    
for i in range(len(b)):
    d.append(0)

for i in range(q):
    w=l[i][0]-1
    x=l[i][1]-1
    y=l[i][2]
    z=l[i][3]
    for j in range(len(b)):
        if b[j][x]-b[j][w]==y:
            d[j]+=z

print(max(d))

Solution (Python):
from itertools import combinations_with_replacement
 
n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]
 
ans = 0
for pat in combinations_with_replacement(range(1, m + 1), n):
    score = 0
    for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if pat[b] - pat[a] == c:
            score += d
 
    ans = max(ans, score)
 
print(ans)

Solution (Python):
import copy


def dfs(A):
    global ans
    if len(A) == n + 1:
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return

    B = copy.copy(A)
    B.append(A[-1])
    while B[-1] <= m:
        dfs(B)
        B[-1] += 1


n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q
ans = 0

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

dfs([1])

print(ans)

Solution (Python):
def dfs(A):
    global ans
    if len(A) == n + 1:
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return

    B = list(A)
    B.append(A[-1])
    while B[-1] <= m:
        dfs(tuple(B))
        B[-1] += 1


n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q
ans = 0

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

dfs(tuple([1]))

print(ans)

Solution (Python):
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q
ans = 0

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

for seq in combinations_with_replacement([i for i in range(1, m+1)], n):
    now = 0
    for j in range(q):
        if seq[b[j] - 1] - seq[a[j] - 1] == c[j]:
            now += d[j]
    ans = max(ans, now)

print(ans)

Solution (Python):
import numpy as np
import itertools

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

A = np.array(list(itertools.combinations_with_replacement(range(1,M+1),N)))

n = len(A)
s = np.zeros(n, np.int32)

for i in range(Q):
    a, b, c, d = map(int,input().split())
    s += d * (A[:,b-1] - A[:,a-1] == c)

print(max(s))

Solution (Python):
from collections import deque

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(Q)]

def calc(seq):
    points = 0
    for a,b,c,d in abcd:
        if seq[b-1]-seq[a-1]==c:
            points += d
    return points

q = deque()
q.append([1])
ans = 0
while q:
    head = q.popleft()
    if len(head)==N:
        pts = calc(head)
        ans = max(ans, pts)
    else:
        for i in range(head[-1], M+1):
            new = head + [i]
            q.append(new)

print(ans)

Solution (Python):
from itertools import combinations_with_replacement
import numpy as np 
N,M,Q = (int(x) for x in input().split())
abcd =np.zeros((Q,4),dtype=int)
for i in range(Q):
    abcd[i] = list(map(int, input().split()))
abcd[:,0] -=1 
abcd[:,1] -=1 


ans =[]

for a in combinations_with_replacement (range(1,M+1),N):
    A =np.array(a,dtype=int)
    X = np.where( A[abcd[:,1] ] -A[abcd[:,0]] ==abcd[:,2] )
    ans.append(np.sum(abcd[X,3]))
print(max(ans))

Solution (Python):
import itertools

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

a, b, c, d = [], [], [], []
for i in range(Q):
    _a, _b, _c, _d = map(int, input().split())
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

l = [v for v in range(1, M+1)]
ll = list(itertools.combinations_with_replacement(l, N))

ans = 0
for i in ll:
    anstmp = 0
    for j in range(Q):
        if i[b[j]-1] - i[a[j]-1] == c[j]:
            anstmp += d[j]
    if anstmp > ans:
        ans = anstmp

print(ans)

Solution (Python):
import itertools

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

a, b, c, d = [], [], [], []
for i in range(Q):
    _a, _b, _c, _d = map(int, input().split())
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

l = [v for v in range(1, M+1)]
ll = list(itertools.combinations_with_replacement(l, N))

ans = 0
for i in ll:
    anstmp = 0
    for j in range(Q):
        if i[b[j]-1] - i[a[j]-1] == c[j]:
            anstmp += d[j]
    if anstmp > ans:
        ans = anstmp

print(ans)

Solution (Python):
import itertools

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

abcd = [tuple(map(int, input().split())) for _ in range(Q)]

Max = 0

for C in itertools.combinations_with_replacement(range(1, M + 1), N):
  score = sum([d for a, b, c, d in abcd if C[b-1] - C[a-1] == c])
  Max = max(Max, score)
print(Max)

Solution (Python):
from collections import deque
de = deque()
n,m,q = map(int,input().split())
queries = []
for _ in range(q):
    a,b,c,d = map(int,input().split())
    queries.append((a,b,c,d))
de.append([1])
maxscore = 0
while de:
    li = de.popleft()
    if len(li) < n:
        for i in range(li[-1],m+1):
            new_li = li + [i]
            de.append(new_li)
    else:
        score = 0
        for i in range(q):
            a,b,c,d = queries[i]
            if li[b-1] - li[a-1] == c:
                score += d
        maxscore = max(maxscore,score)
print(maxscore)

Solution (Python):
n,m,q = map(int,input().split())
li = [i for i in range(1,m+1)]
lin = []

for _ in range(q):
    a,b,c,d = map(int,input().split())
    lin.append((a,b,c,d))

from itertools import combinations_with_replacement
li = list(combinations_with_replacement(li, n))
ma = 0

for i in li:
    point = 0
    for j in lin:
        a,b,c,d = j
        a -= 1
        b -= 1
        if i[b]-i[a] == c:
            point += d
    ma = max(point,ma)

print(ma)

Solution (Python):

import itertools
n,m,q=map(int,input().split())
l=list(itertools.combinations_with_replacement(range(1,m+1),n))
res=[0]*len(l)
for i in range(q):
 a,b,c,d=map(int,input().split())
 for j,x in enumerate(l):
  if x[b-1]-x[a-1]==c:
   res[j]+=d
print(max(res))

Solution (Python):
N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]
ans = 0
def calc(p):
    ret = 0
    for a, b, c, d in abcd:
        a, b = a-1, b-1
        if p[b] - p[a] == c:
            ret += d
    return ret

def dfs(a, d):
    global ans
    if d == N:
        ans = max(ans, calc(a))
        return
    for i in range(a[-1], M+1):
        dfs(a+[i], d+1)

for i in range(1, M+1):
    dfs([i], 1)

print(ans)

Solution (Python):
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

ans = 0
for pat in combinations_with_replacement(range(1, m + 1), n):
    score = 0
    for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if pat[b] - pat[a] == c:
            score += d

    ans = max(ans, score)

print(ans)

Solution (Python):
from itertools import combinations
N,M,Q = map(int,input().split())
B = []
for j in range(Q):
    b = list(map(int,input().split()))
    B.append(b)
cmax = 0
for k in range(1,N+1):
    for x in combinations(range(1,M+1),k):
        for y in combinations(range(N-1),k-1):
            A = [0 for _ in range(N)]
            curx = 0
            cury = 0
            for i in range(N):
                if cury==k-1 or i<=y[cury]:
                    A[i]=x[curx]
                else:
                    cury += 1
                    curx += 1
                    A[i] = x[curx]
            cnt = 0
            for j in range(Q):
                a,b,c,d = B[j]
                if A[b-1]-A[a-1]==c:
                    cnt += d
            cmax = max(cmax,cnt)
print(cmax)

Solution (Python):
n, m, q = map(int, input().split())
X = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    a, b = a-1, b-1
    X.append((a, b, c, d))

import itertools
ans = -1
for C in itertools.combinations_with_replacement(range(m), n):
    temp = 0
    for i in range(q):
        a, b, c, d = X[i]
        if C[b]-C[a] == c:
            temp += d
    ans = max(ans, temp)
print(ans)

Solution (Python):
from itertools import combinations_with_replacement
N,M,Q = map(int,input().split())

abcd = [tuple(map(int,input().split())) for _ in range(Q)]

ans = 0
for n in combinations_with_replacement(range(1,M+1),N):
    tmp = 0
    for a,b,c,d in abcd:
        if n[b-1] - n[a-1] == c:
            tmp += d
    
    ans = max(ans,tmp)


print(ans)

Solution (Python):
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(q):
  A,B,C,D=map(int,input().split())
  a.append(A)
  b.append(B)
  c.append(C)
  d.append(D)
ans=0
M=[0,0,0,0,0,0,0,0,0,0,0]
for i in range(n):
  M[i]=1
cursor=n
breakflag=0
while True:
  ev=0
  for i in range(q):
    if M[b[i]-1]-M[a[i]-1]==c[i]:
      ev+=d[i]
  if ev>ans:
    ans=ev
  while True:
    if M[cursor-1]<m:
      M[cursor-1]+=1
      for i in range(cursor,n):
        M[i]=M[cursor-1]
      cursor=n
      break
    cursor-=1
    if cursor==0:
      breakflag=1
      break
  if breakflag==1:
    break
print(ans)

Solution (Python):
n, m, q = map(int, input().split())
a, b, c, d = [0] * q, [0] * q, [0] * q, [0] * q
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

'''
1.数列を生成する。
2.配列ごとに得点を求める。
'''
def judge(L):
    score = 0
    for i in range(q):
        check = L[b[i] - 1] - L[a[i] - 1]
        if check == c[i]:score += d[i]

    return score

def dfs(L):
    global score
    if len(L) == n:
        temp = judge(L)
        if temp > score:score = temp
        return 

    start = L[-1] if len(L) != 0 else 1
    for v in range(start, m + 1):
        L.append(v)
        dfs(L)
        L.pop()


score = 0
dfs([])
print(score)

Solution (Python):
from itertools import combinations_with_replacement as cbr
N,M,Q = list(map(int, input().split()))
X = []
for _ in range(Q):
  X.append(list(map(int, input().split())))
  
ans = -1
for p in cbr(range(1,M+1), N):
  wk = 0
  for x in X:
    a,b,c,d = x
    if p[b-1] - p[a-1] == c:
      wk += d
  ans = max(wk,ans)
  
print(ans)

Solution (Python):
from itertools import combinations_with_replacement as cbr
N,M,Q = list(map(int, input().split()))
X = []
for _ in range(Q):
  X.append(list(map(int, input().split())))
  
ans = -1
for p in cbr(range(1,M+1), N):
  wk = 0
  for x in X:
    a,b,c,d = x
    if p[b-1] - p[a-1] == c:
      wk += d
  ans = max(wk,ans)
  
print(ans)

Solution (Python):
from sys import stdin
from itertools import combinations_with_replacement

input = stdin.readline
N,M,Q = map(int, input().split())
numlist = [i for i in range(1,M+1)]
A = [0]*(Q+1)
B = [0]*(Q+1)
C = [0]*(Q+1)
D = [0]*(Q+1)
for q in range(1,Q+1):
    A[q],B[q],C[q],D[q] = map(int, input().split())

maxscore = 0
for tpl in combinations_with_replacement(numlist,N):
    score = 0
    for q in range(1,Q+1):
        if tpl[B[q]-1] - tpl[A[q]-1] == C[q]:
            score += D[q]
    maxscore = max(maxscore, score)
print(maxscore)

Solution (Python):
N, M, Q = map(int, input().split())

lst = []
for i in range(Q):
  lst.append(list(map(int, input().split())))
  
  
import itertools






A_pattern = itertools.combinations_with_replacement(range(1, M+1), N)
ans = 0

for a in A_pattern:
  point = 0
  
  for l in lst:
    if a[l[1]-1] - a[l[0]-1] == l[2]:
      point += l[3]
      
  if ans < point:
    ans = point
    
print(ans)

Solution (Python):
import itertools
N, M, Q = map(int, input().split())
abcd = []
ans = 0
for i in range(Q):
  abcd.append(input())
for X in itertools.combinations_with_replacement(range(1, M + 1), N):
  tmp = 0
  for z in abcd:
    a, b, c, d = map(int, z.split())
    if X[b - 1] - X[a - 1] == c:
      tmp += d
  ans = max(ans, tmp)
print(ans)

Solution (Python):
import copy

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

def dfs(count, pre, ls):
    if count == N:
        temp = copy.copy(ls)
        num.append(temp)
        return

    for n in range(pre, M+1):
        ls[count] = n
        dfs(count+1, n, ls)
        ls[count] = 0

num = []
ls = [0] * N
dfs(0, 1, ls)

q = [[int(i) for i in input().split()] for j in range(Q)]
ans = 0
for i in range(len(num)):
    n = num[i]
    score = 0
    for j in range(Q):
        a, b, c, d = q[j]
        if n[b-1] - n[a-1] != c:
            continue
        score += d
    else:
        ans = max(ans, score)

print(ans)

Solution (Python):
n,m,q = [int(_) for _ in input().split()]

a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

for i in range(q):
  a[i],b[i],c[i],d[i] = [int(_) for _ in input().split()]
  a[i] = a[i]-1 
  b[i] = b[i]-1

def score(A):
  tmp = 0
  for ai,bi,ci,di in zip(a,b,c,d):
    if A[bi] - A[ai] == ci:
      tmp += di
  return tmp


def dfs(A):
  if len(A) == n: 
    return score(A)
  if len(A) > 0: 
    prev_last = A[-1]
  else:
    prev_last = 1
  result = 0
  for v in range(prev_last,m+1):
    A.append(v)
    result = max(result,dfs(A))
    A.pop()
  return result

print(dfs([]))

Solution (Python):
N,M,Q = map(int,input().split())
ls_rq = [list(map(int, input().split())) for i in range(Q)]


As=[]
from queue import LifoQueue as lq
S=lq()
S.put([])
while not S.empty():
  a=S.get()
  if len(a)==N:
    As.append(a)
  else:
    if len(a)==0:
      b=1
    else:
      b=a[-1]
    for  i in range(b,M+1):
      S.put(a+[i])


ls_score=[]
for ls in As:
  score=0
  for j in range(Q):
    if ls[ls_rq[j][1]-1]-ls[ls_rq[j][0]-1]==ls_rq[j][2]:
      score+=ls_rq[j][3]
  ls_score.append(score)    
  score=0


ans=max(ls_score)  
print(ans)

Solution (Python):
N,M,Q = map(int,input().split())
ls_rq = [list(map(int, input().split())) for i in range(Q)]


As=[]
from queue import LifoQueue as lq
S=lq()
S.put([])
while not S.empty():
  a=S.get()
  if len(a)==N:
    As.append(a)
  else:
    if len(a)==0:
      b=1
    else:
      b=a[-1]
    for  i in range(b,M+1):
      S.put(a+[i])


ls_score=[]
for ls in As:
  score=0
  for j in range(Q):
    if ls[ls_rq[j][1]-1]-ls[ls_rq[j][0]-1]==ls_rq[j][2]:
      score+=ls_rq[j][3]
  ls_score.append(score)    
  score=0


ans=max(ls_score+[0])  
print(ans)

Solution (Python):
N,M,Q = map(int,input().split())
ls_rq = [list(map(int, input().split())) for i in range(Q)]


As=[]
from queue import LifoQueue as lq
S=lq()
S.put([])
while not S.empty():
  a=S.get()
  if len(a)==N:
    As.append(a)
  else:
    if len(a)==0:
      b=1
    else:
      b=a[-1]
    for  i in range(b,M+1):
      S.put(a+[i])


ls_score=[]
for ls in As:
  score=0
  for j in range(Q):
    if ls[ls_rq[j][1]-1]-ls[ls_rq[j][0]-1]==ls_rq[j][2]:
      score+=ls_rq[j][3]
  ls_score.append(score)    
  score=0


ans=max(ls_score+[0])  
print(ans)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N, M, Q = map(int, readline().split())

kumi = []
for _ in range(Q):
    tmp = list(map(int, readline().split()))
    kumi.append(tmp)

ans = 0
res = []
def F(l):
    if len(l) == N:
        ans = 0
        for i in range(Q):
            a, b, c, d = kumi[i]
            if l[b-1] - l[a-1] == c:
                ans += d
        return ans
    ans = 0
    start = l[-1] if len(l) else 0
    for i in range(start, M):
        l.append(i)
        ans = max(ans, F(l))
        l.pop()
    return ans
    
ans = F([])
print(ans)

Solution (Python):
import sys
from itertools import combinations_with_replacement as cwr
input = sys.stdin.readline

def dfs(n,m):
    adj = {}
    for i in range(1,m+1):
        adj[i] = [j for j in range(i,m+1)]
    
    stack = [[i] for i in range(1,m+1)]
    combs = []
    while stack:
        node = stack.pop()
        if len(node) == n:
            combs.append(node)
        else:
            for child in adj[node[-1]]:
                cand = node+[child]
                stack.append(cand)
    return combs


N,M,Q = map(int,input().split())
A,B,C,D = [],[],[],[]
for i in range(Q):
    a,b,c,d = map(int,input().split())
    a,b = a-1, b-1
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

ans = 0
combs = dfs(N,M)


ans = [0]*(len(combs))
for i,comb in enumerate(combs):
    for a,b,c,d in zip(A,B,C,D):
        if comb[b] - comb[a] ==c:
            ans[i] += d
print(max(ans))

Solution (Python):
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
aa=[]
bb=[]
cc=[]
dd=[]
for i in range(q):
  a,b,c,d=map(int,input().split())
  aa.append(a-1)
  bb.append(b-1)
  cc.append(c)
  dd.append(d)
sumd=[]

for Alis in combinations_with_replacement(range(1,m+1),n):
  
  di=0
  
  for i in range(q):
    if cc[i]==(Alis[bb[i]]-Alis[aa[i]]):
      di+=dd[i]
      
  sumd.append(di)
print(max(sumd))

Solution (Python):
N, M, Q = map(int, input().split())
integer_list = [list(map(int, input().split())) for i in range(Q)]
ans, use_cnt, unuse_cnt = 0, 0, 0
use_num_list = [0]
combi_list = []

def combi(use_num_list):
    for i in range(max(use_num_list), M):
        if len(use_num_list) == N:
            combi_list.append(use_num_list[1:] + [i])
            continue
        else:
            combi(use_num_list + [i])

combi(use_num_list)

for cmb in combi_list:
    tmp_ans = 0
    for int_combi in integer_list:
        if cmb[int_combi[1] - 1] - cmb[int_combi[0] - 1] == int_combi[2]:
            tmp_ans += int_combi[3]
    
    ans = max(ans, tmp_ans)
print(ans)

Solution (Python):
def main():
    n, m, q = map(int, input().split())
    a = [0] * q
    b = [0] * q
    c = [0] * q
    d = [0] * q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())

    def cal(A):
        ans = 0
        for ai, bi, ci, di in zip(a, b, c, d):
            if A[bi-1] - A[ai-1] == ci:
                ans += di
        return ans

    def dfs(A):
        if len(A) == n:
            return cal(A)
        res = 0
        pre = A[-1] if len(A) > 0 else 1
        for i in range(pre, m+1):
            A.append(i)
            res = max(dfs(A), res)
            A.pop()
        return res

    print(dfs([]))

if __name__ == '__main__':
    main()

Solution (Python):
n, m, q = map(int, input().split())
data = [list(map(int, input().split())) for i in range(q)]

def listup(n, m):
    d = []
    c = [1 for i in range(n)]
    while True:
        d.append(tuple(c))
        if c == [m for i in range(n)]:
            break
        c[n - 1] += 1
        if c[n - 1] > m:
            for i in range(n - 1):
                if c[n - 2 - i] == m:
                    continue
                c[n - i - 2] += 1
                for j in range(i + 1):
                    c[n - i - 1 + j] = c[n - i - 2]
                break
    return d

d = listup(n, m)
dmax = 0
for i in range(len(d)):
    cura = d[i]
    di = 0
    for j in range(q):
        if cura[data[j][1] - 1] - cura[data[j][0] - 1] == data[j][2]:
            di += data[j][3]
    if dmax < di:
        dmax = di

print(dmax)

Solution (Python):
N,M,Q = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(Q)]
def dfs(s):
    if len(s) == N:
        return[s]
    result = []
    if s == '':
        num = 0
    else:
        num = int(s[-1])
    for i in range(num,M):
        result.extend(dfs(s+str(i)))
    return result
ans = 0
S = dfs('')
for s in S:
    C = [int(i)+1 for i in s]
    B = 0
    for a,b,c,d in A:
        if C[b-1] - C[a-1] == c:
            B += d
    ans = max(ans,B)
print(ans)

Solution (Python):
import sys
import itertools

import time
import math

sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

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

n, m, q = map(int, readline().split())

a = [0 for _ in range(q)]
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
d = [0 for _ in range(q)]

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, readline().split())

A = [1]
ans = 0
def dfs():
    if len(A) == n + 1:
        acc = 0
        for i in range(q):
            if A[b[i]] - A[a[i]] == c[i]:
                acc += d[i]
        global ans
        ans = max(ans, acc)
        return
    A.append(A[-1])
    while A[-1] <= m:
        dfs()
        A[-1] += 1
    A.pop()

dfs()
print(ans)

Solution (Python):
n,m,q = map(int,input().split())
abcd = []
for i in range(q):
    abcd.append(list(map(int,input().split())))
ans = 0

def dfs(s):
    if len(s) == n:
        global ans
        count = 0
        for a,b,c,d in abcd:
            a -= 1
            b -= 1
            if s[b] - s[a] == c:
                count += d
        ans = max(ans, count)
        return
    for i in range(s[-1], m+1):
        dfs(s + [i])
for i in range(1,m+1):
    dfs([i])
print(ans)

Solution (Python):
n,m,q = map(int,input().split())
abcd = []
for i in range(q):
    abcd.append(list(map(int,input().split())))
ans = 0

def dfs(s):
    if len(s) == n:
        global ans
        count = 0
        for a,b,c,d in abcd:
            a -= 1
            b -= 1
            if s[b] - s[a] == c:
                count += d
        ans = max(ans, count)
        return
    for i in range(s[-1], m+1):
        dfs(s + [i])
for i in range(1,m+1):
    dfs([i])
print(ans)

Solution (Python):
import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N, M, Q = map(int, readline().split())

kumi = []
for _ in range(Q):
    tmp = list(map(int, readline().split()))
    kumi.append(tmp)

ans = 0
res = []
def F(l):
    if len(l) == N:
        ans = 0
        for i in range(Q):
            a, b, c, d = kumi[i]
            if l[b-1] - l[a-1] == c:
                ans += d
        yield ans
        return
    start = l[-1] if len(l) else 0
    for i in range(start, M):
        l.append(i)
        yield from F(l)
        l.pop()
    
ans = max(F([]))
print(ans)

Solution (Python):
n,m,q=map(int,input().split())
abcd=[[int(j)for j in input().split()]for i in range(q)]
ans=0
import itertools
for l in itertools.combinations_with_replacement(range(1,m+1),n-1):
    tmp=0
    for a,b,c,d in abcd:
        p,q=0,0
        if a==1:
            p,q=l[b-2],1
        else:
            p,q=l[b-2],l[a-2]
        if p-q==c:
            tmp+=d
    ans=max(ans,tmp)
print(ans)

Solution (Python):
from itertools import combinations_with_replacement
N,M,Q=map(int,input().split())
G=[]
for _ in range(Q):
  A,B,C,D=map(int,input().split())
  G.append([A,B,C,D])

max_score=0
for A in combinations_with_replacement(range(1,M+1),r=N):  
  score=0
  for a,b,c,d in G:
    if A[b-1]-A[a-1]==c:
      score+=d
    max_score=max(max_score,score)
print(max_score)

Solution (Python):
N, M, Q = map(int, input().split(' '))
records = [tuple(map(int, input().split(' '))) for _ in range(Q)]

max_score = 0


def dfs(start, end, depth, numbers):
    if depth == N:
        global max_score
        for n in range(start, end + 1):
            A = (*numbers, n)
            score = 0
            for a, b, c, d in records:
                if A[b - 1] - A[a - 1] == c:
                    score += d
            max_score = max(max_score, score)
    else:
        for n in range(start, end + 1):
            dfs(start=n, end=end, depth=depth + 1, numbers=(*numbers, n))


dfs(start=1, end=M, depth=1, numbers=())
print(max_score)

Solution (Python):
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split(' '))
records = [tuple(map(int, input().split(' '))) for _ in range(Q)]

max_score = 0

for A in combinations_with_replacement(range(1, M + 1), r=N):
    score = 0
    for a, b, c, d in records:
        if A[b - 1] - A[a - 1] == c:
            score += d
    max_score = max(max_score, score)

print(max_score)

Solution (Python):
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split(' '))
records = [tuple(map(int, input().split(' '))) for _ in range(Q)]

max_score = 0

for A in combinations_with_replacement(range(1, M + 1), r=N):
    A = sorted(A)
    score = 0
    for a, b, c, d in records:
        if A[b - 1] - A[a - 1] == c:
            score += d
    max_score = max(max_score, score)

print(max_score)

Solution (Python):
n,m,q = map(int,input().split())
abcd = [[*map(int,input().split())] for _ in range(q)]

def dfs(A=[1]): 
    if n+1 <= len(A):
        return sum(d if A[b]-A[a]==c else 0 for a,b,c,d in abcd)
    A.append(A[-1])
    ret = 0
    while A[-1] <= m:
        ret = max(ret, dfs(A))
        A[-1] += 1
    A.pop()
    return ret

ans = dfs()
print(ans)

Solution (Python):
from itertools import *
n, m, q = map(int, input().split())

a, b, c, d = [], [], [], []

for i in range(q):
    a_temp, b_temp, c_temp, d_temp = map(int, input().split())
    a.append(a_temp)
    b.append(b_temp)
    c.append(c_temp)
    d.append(d_temp)

A = list(combinations_with_replacement(range(1,m + 1),n))

ans = 0
ans_i = 0

for A_i in A:
    for i in range(q):
        if A_i[b[i] - 1] - A_i[a[i] - 1] == c[i]:
            ans_i += d[i]

    ans = max(ans, ans_i)
    ans_i = 0

print(ans)

Solution (Python):
def dfs(A, d):
    ans = 0
    if d == N:
        for a, b, c, d in ABCD:
            if A[b] - A[a] == c:
                ans += d
        return ans
    if A:
        s = A[-1]
    else:
        s = 1
    for i in range(s, M+1):
        ans = max(ans, dfs(A+[i], d+1))
    return ans

N, M, Q = map(int, input().split())
ABCD = []
for q in range(Q):
    a, b, c, d = map(int, input().split())
    ABCD += [[a-1, b-1, c, d]]

print(dfs([], 0))

Solution (Python):
n, m, q = map(int, input().split())
abcd = [[] for j in range(q)]
for i in range(q):
    abcd[i] = list(map(int, input().split()))
l = [1] * n


def plus():
    l[n - 1] += 1
    while m + 1 in l:
        a = l.index(m + 1)
        l[a - 1] += 1
        for i in range(a, n):
            l[i] = l[a - 1]


ans = 0
while l[0] <= m:
    score = 0
    for i in range(q):
        if l[abcd[i][1] - 1] - l[abcd[i][0] - 1] == abcd[i][2]:
            score += abcd[i][3]
    if ans < score:
        ans = score
    plus()

print(ans)

Solution (Python):
n,m,q = map(int,input().split())
abcd = [[] for j in range(q)]
for i in range(q):
    abcd[i] = list(map(int,input().split()))
l = [1]*n
l[n-1]=m
def plus():
    l[n-2] += 1
    while m+1 in l:
        a = l.index(m+1)
        l[a-1]+=1
        for i in range(a,n-1):
            l[i] = l[a-1]

ans=0
while l[0]<=m:
    score = 0
    for i in range(q):
        if l[abcd[i][1]-1]-l[abcd[i][0]-1]==abcd[i][2]:
            score += abcd[i][3]
    if ans < score:
        ans = score
    plus()


print(ans)

Solution (Python):
n,m,q = map(int,input().split())
abcd = [[*map(int,input().split())] for _ in range(q)]
from itertools import *
ans = 0
for A in combinations_with_replacement(range(1, m+1), n): 
    now = sum(d if A[b-1] - A[a-1] == c else 0 for a,b,c,d in abcd)
    ans = max(ans, now)
print(ans)

Solution (Python):
n,m,q = map(int,input().split())
abcd = [[*map(int,input().split())] for _ in range(q)]
from itertools import *
ans = 0
for A in combinations_with_replacement(range(1, m+1), n): 
    now = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c: now += d
    ans = max(ans, now)
print(ans)

Solution (Python):
N, M, Q = map(int, input().split())
ABCD = []
for i in range(Q):
    A, B, C, D = map(int, input().split())
    ABCD.append((A, B, C, D))

def solve(N, M, Q, ABCD):
    As = []
    dfs(As, [1], N)
    answer = 0
    for A in As:
        point = 0
        for a, b, c, d in ABCD:
            point += d if A[b] - A[a] == c else 0
        answer = max(answer, point)
    print(answer)


def dfs(As, A, N):
    if len(A) == N+1:
        As.append(A)
        return
    a = A[-1]
    for b in range(a, M+1):
        A_ = A[:]
        A_.append(b)
        dfs(As, A_, N)
    
solve(N, M, Q, ABCD)

Solution (Python):
N, M, Q = map(int,input().split())
a_d = [list(map(int,input().split())) for _ in range(Q)]

ans = 0
for i1 in range(1,M+1):
    for i2 in range(i1,M+1):
        for i3 in range(i2,M+1):
            for i4 in range(i3,M+1):
                for i5 in range(i4,M+1):
                    for i6 in range(i5,M+1):
                        for i7 in range(i6,M+1):
                            for i8 in range(i7,M+1):
                                for i9 in range(i8,M+1):
                                    for i10 in range(i9,M+1):
                                        A = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        tmp = 0
                                        for a,b,c,d in a_d:
                                            if A[b-1]-A[a-1] == c:
                                                tmp += d
                                        ans = max(ans,tmp)
print(ans)

Solution (Python):
import itertools
N, M, Q = map(int, input().split())
abcd = [ list(map(int, input().split())) for _ in range(Q) ]

res = 0
for product in itertools.combinations_with_replacement(range(1, M+1), N):
  S = 0
  for a,b,c,d in abcd:
    if product[b-1] - product[a-1] == c:
      S += d
  res = max(res, S)

print(res)

Solution (Python):
n,m,q = map(int,input().split())
ab = [0]*q
for i in range(q):
    ab[i] = list(map(int,input().split()))
import itertools
data = list(range(m))
r = n
c = list(itertools.combinations_with_replacement(data, r))
ans = 0
for L in c:
    m = 0
    for i in range(q):
        if L[ab[i][1]-1] - L[ab[i][0]-1] == ab[i][2]:
            m += ab[i][3]
    ans = max(ans,m)
print(ans)