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):
from collections import deque
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=deque()  
def make(a,b,c): 
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            make(a+[i],b,c)
for t in range(1,m+1):
    make([t],n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

Solution (Python):
import math
from collections import deque
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=deque()  
def make(a,b,c): 
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            make(a+deque([i]),b,c)
for t in range(1,m+1):
    make(deque([t]),n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

Solution (Python):
from collections import deque
from copy import copy

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

queue = deque()
for i in range(1, M+1):
    queue.append([i])
while queue[0] != [1] * N:
    x = queue.popleft()
    for i in range(x[-1], M+1):
        y = copy(x)
        y.append(i)
        queue.append(y)

score_max = 0
for A in queue:
    score = 0
    for a, b, c, d in X:
        if A[b-1] - A[a-1] == c:
            score += d
    score_max = max(score, score_max)

print(score_max)

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

ABCD = [list(map(int, input().split())) for i in range(Q)]

import itertools

max_point = 0
for i in itertools.combinations_with_replacement(range(1, M+1), N):
    
    point = 0
    for abcd in ABCD:
        if i[abcd[1]-1] - i[abcd[0]-1] == abcd[2]:
            point += abcd[3]
    max_point = max(max_point, point)
print(max_point)

Solution (Python):
import copy
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=list()  
def make(a,b,c): 
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            make(a+[i],b,c)
for t in range(1,m+1):
    make([t],n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

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

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

l = []
def dfs(lis, y):
  if len(lis) == N:
    l.append(lis)
    return
  else:
    for i in range(y, M+1):
      z = list(lis)
      z.append(i)
      dfs(z, i)
    return
      
dfs([], 1)

ans = 0
for A in l:
  tmp = 0
  for a, b, c, d in query:
    if A[b-1] - A[a-1] == c:
      tmp += d
  ans = max(ans, tmp)

print(ans)

Solution (Python):
'''ika tako
制約条件を見て、戦略を決める（制約が戦略を決める）
配列の添え字を、なるべくシンプルにする（KISS）
広義単調増加（同じ数もOK）なので、重複順列（仕切り板で分ける）
求める数列の候補である　重複順列を列挙し、重複順列毎にscoreを求め、
そのscoreの最大値が答（数列を求めるのではなく、数列を点検する）
入力は空のリストにappendで追加
入力の際、0-indexとなるように、引く1をする（後で考えるのはメンドウ）
重複順列毎に回し、更に、クエリ毎に条件式で得点を求める、二重ループ
scoreは、答の候補である重複順列毎の得点
求めるansは、そのscoreの最大値
この二つを区別すること
'''

from itertools import combinations_with_replacement
 
n, m, q = map(int, input().split())
queries = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    queries.append((a, b, c, d))

ans = 0
for arr in combinations_with_replacement(range(m), n):
    score = 0
    for a, b, c, d in queries:
        if arr[b] - arr[a] == c:
            score += d
    ans = max(ans, score)

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
n,m,q = map(int,input().split())
query = [[int(i) for i in input().split()] for _ in range(q)]

def f(A):
    if len(A) == n+1:
        
        cnt = 0
        for i in range(q):
            a,b,c,d = query[i]
            if A[b]-A[a] == c: cnt += d
        return cnt
    res = 0
    for i in range(A[-1],m+1):
        res = max(res,f(A+[i]))
    return res

print(f([1]))

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

ans = 0
a = [0 for i in range(n)]
def dfs(p):
    global ans
    if p == 0:
        for i in range(1, m+1):
            a[p] = i
            dfs(p+1)
    else:
        for i in range(a[p-1], m+1):
            a[p] = i
            if p != n-1:
                dfs(p+1)
            else:
                temp = 0
                for j in range(q):
                    ai, bi, ci, di = kumi[j]
                    ai, bi = ai-1, bi-1
                    if a[bi] - a[ai] == ci:
                        temp += di
                ans = max(ans, temp)

dfs(0)
print(ans)

Solution (Python):
from itertools import combinations_with_replacement

n, m, q = map(int, input().split())
p = []
ans = 0
for _ in range(q):
    p.append(list(map(int, input().split())))
for A in combinations_with_replacement(range(1,m+1), n):
    cnt = 0
    for i in range(q):
        if A[p[i][1]-1] - A[p[i][0]-1] == p[i][2]:
            cnt += p[i][3]
    ans = max(ans, cnt)
print(ans)

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

x = list(combinations_with_replacement(range(1,m+1),n))
y = []
for _ in range(q):
  a,b,c,d = map(int, input().split())
  y.append([a,b,c,d])
  
ans = 0
for i in x:
  k = 0
  for j in y:
    if i[j[1]-1] - i[j[0]-1] == j[2]:
      k += j[3]
  ans = max(ans,k)
print(ans)

Solution (Python):
import copy
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=list()  
def make(a,b,c): 
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            k=copy.copy(a)
            k.append(i)
            make(k,b,c)
for t in range(1,m+1):
    make([t],n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

Solution (Python):
import itertools

N, M, Q = map(int, input().split())
ABCD = []
ans = 0

for _ in range(Q):
    ai, bi, ci, di = map(int, input().split())
    ABCD.append((ai, bi, ci, di))

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

for a in A:
    tmp = 0
    for abcd in ABCD:
        if a[abcd[1]-1] - a[abcd[0]-1] == abcd[2]:
            tmp += abcd[3]
    ans = max(ans, tmp)
print(ans)

Solution (Python):
import itertools
n,m,q = map(int,input().split())
li = []
for _ in range(q):
    li.append(list(map(int,input().split())))
kumi = list(itertools.combinations_with_replacement(range(1,m+1), n))
score = 0
for k in kumi:
    each_score = 0
    for l in li:
        a = l[0]
        b = l[1]
        diff = l[2]
        katen = l[3]
        if k[b-1]-k[a-1] == diff:
            each_score += katen
    if each_score > score:
        score = each_score
print(score)

Solution (Python):
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())

  
from copy import deepcopy

ans_list=[]
def dfs(x,M,N,ans):
  if len(ans)<=N-1:
    for j in range(x,M+1):
      tmp=deepcopy(ans)
      tmp.append(j)
      if len(tmp)==N:
        ans_list.append(tmp)
      else:
        dfs(j,M,N,tmp)
    
q=dfs(1,M,N,[])


f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

Solution (Python):
import itertools
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, Q = map(int, input().split())
    A_ = itertools.combinations_with_replacement(range(1, M + 1), N)
    abcd = []
    for _ in range(Q):
        a, b, c, d = map(int, input().split())
        a -= 1
        b -= 1
        abcd.append((a, b, c, d))

    ans = 0
    for A in A_:
        tmp = 0
        for a, b, c, d in abcd:
            if A[b] - A[a] == c:
                tmp += d

        if tmp > ans:
            ans = tmp

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import copy
n,m,q=[int(_) for _ in input().split()]
lista=[[int(i) for i in input().split()] for j in range(q)]
v=list()  
def make(a,b,c): 
    global v
    if len(a)==b:
        v.append(a)
    else:
        for i in range(a[-1],c+1):
            k=copy.copy(a)
            k.append(i)
            make(k,b,c)
for t in range(1,m+1):
    make([t],n,m)
max=0
for j in v:
    point=0
    for l in lista:
        if j[l[1]-1]-j[l[0]-1]==l[2]:
            point+=l[3]
    if max<point:
        max=point
print(max)

Solution (Python):
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())

  
from copy import deepcopy

ans_list=[]
def dfs(x,M,N,ans):
  if len(ans)<=N-1:
    for j in range(x,M+1):
      tmp=deepcopy(ans)
      tmp.append(j)
      if len(tmp)==N:
        ans_list.append(tmp)
      else:
        dfs(j,M,N,tmp)
    
q=dfs(1,M,N,[])


f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

Solution (Python):
def dfs(arr, min_nx):
    ans = 0
    if len(arr) == n:
        tmp = 0
        for a,b,c,d in lst:
            if arr[b-1] - arr[a-1] == c:
                tmp += d
        return tmp
    else:
        for nx in range(min_nx, m+1):
            new_arr = arr + [nx]
            score = dfs(new_arr, nx)
            ans = max(ans, score)
    return ans
n,m,q = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(q)]
ans = dfs([], 1)
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() )
  A = [1] * (n + 1)
  A[0] = 0
  ans = 0
  while A[0]==0:
    tmp = 0
    for i in range(q):
      if( A[b[i]]-A[a[i]]==c[i] ):
        tmp += d[i]
    ans = max(ans, tmp)
    A[n] += 1
    for i in range(1,n+1):
      if( A[i]>m ):
        i-=1
        A[i] += 1
        t = A[i]
        for j in range(i,n+1):
          A[j] = t
        break
  print(ans)

main()

Solution (Python):
import itertools

n,m,q = map(int, input().split())
A = list(itertools.combinations_with_replacement(range(1, m+1), n))
qs = [list(map(int, input().split())) for _ in range(q)]
ans = 0
for t in A:
  temp = 0
  for a,b,c,d in qs:
    if t[b-1] - t[a-1] == c:
      temp += d
  ans = max(ans, temp)
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() )
  A = [1] * (n + 1)
  A[0] = 0
  ans = 0
  while A[0]==0:
    tmp = 0
    for i in range(q):
      if( A[b[i]]-A[a[i]]==c[i] ):
        tmp += d[i]
    ans = max(ans, tmp)
    A[n] += 1
    for i in range(1,n+1):
      if( A[i]>m ):
        i-=1
        A[i] += 1
        t = A[i]
        for j in range(i,n+1):
          A[j] = t
        break
  print(ans)

main()

Solution (Python):
from itertools import combinations_with_replacement

N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for i in range(Q)]
ans = 0
for x in combinations_with_replacement(range(1, M+1), 10):
    tmp = 0

    for a, b, c, d in abcd:
        a -= 1
        b -= 1
        if x[a] + c == x[b]:
            tmp += d
    ans = max(ans, tmp)


print(ans)

Solution (Python):
import sys
from itertools import combinations_with_replacement


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, Q = map(int, input().split())
    L = [list(map(int, input().split())) for _ in range(Q)]
    
    answer = 0
    As = list(combinations_with_replacement([i for i in range(1, M + 1)], N))
    for A in As:
        cnt = 0
        for l in L:
            a = l[0] - 1
            b = l[1] - 1
            c = l[2]
            d = l[3]
            if A[b] - A[a] == c:
                cnt += d
        if answer < cnt:
            answer = cnt
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
def dfs(nums, length, min_lim):
    ans = 0
    if length == n:
        score_ret = 0
        for a,b,c,d in req:
            if nums[b] - nums[a] == c:
                score_ret += d
        return score_ret
    
    else:
        for nu in range(min_lim, m+1):
            new_nums = nums + [nu]
            score = dfs(new_nums, length+1, nu)
            ans = max(ans, score)
    return ans

n,m,q = map(int,input().split())
req = [list(map(int,input().split())) for _ in range(q)]
ans = dfs([-1], 0, 1)
print(ans)

Solution (Python):

n,m,q = list(map(int, input().split()))

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

for i in range(q):
    aa,bb,cc,dd = list(map(int, input().split()))
    a.append(aa)
    b.append(bb)
    c.append(cc)
    d.append(dd)

ans = 0

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

dfs([1])
print(ans)

Solution (Python):
def main(k, s):
    if k == n:
        return sum(d * (s[b] - s[a] == c) for a, b, c, d in abcd)
    return max(main(k + 1, s + [ai]) for ai in range(s[-1], m + 1))

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    print(main(0, [1]))

Solution (Python):
N,M,Q=map(int,input().split())
L = []
for i in range(Q):
  L.append(list(map(int, input().split())))
  L[i][0]-=1
  L[i][1]-=1

import itertools

l =list(range(1,M+1))
ans=0

v=list(itertools.combinations_with_replacement(l,N))

for arr in v:
  score=0
  for a,b,c,d in L:
    if (arr[b] - arr[a])==c:
      
      score+=d
  ans=max(ans,score)
print(ans)

Solution (Python):
import itertools

n,m,q=map(int,input().split())
qry=[]*q
for i in range(q):
    l=list(map(int,input().split()))
    qry.append(l)

ans=0

for l in itertools.combinations_with_replacement(range(1,m+1),n):
    val=0
    for i in range(q):
        if l[qry[i][1]-1]-l[qry[i][0]-1]==qry[i][2]:
            val+=qry[i][3]
    ans=max(ans,val)
    
print(ans)

Solution (Python):
import itertools
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
A=[i for i in range(M)]
for i in itertools.combinations_with_replacement(A,N):
  s=0
  for k in range(Q):
    if i[b[k]-1]-i[a[k]-1]==c[k]:
      s+=d[k]
  maxs=max(maxs,s)
      
print(maxs)

Solution (Python):
def dfs(seq):
    global ans
    if len(seq) == n:
        tmp = 0
        for i in range(q):
            if seq[b[i]] - seq[a[i]] == c[i]:
                tmp += d[i]
        ans = max(tmp, ans)
        return 
       
    if seq == []:
        start=0
    else:
        start = seq[-1]

    for i in range(start,m):
        dfs(seq+[i])

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())
    a[i]-=1; b[i]-=1
    
ans = 0
dfs([])
print(ans)

Solution (Python):
from itertools import combinations_with_replacement as combi

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

def points(A, queries):
    score = 0
    for query in queries:
        a, b, c, d = query
        if A[b-1] - A[a-1] == c:
            score += query[3]
    return score

score = 0
for iter in combi([i for i in range(1, m+1)], n):
    score = max(points(sorted(iter), queries), score)

print(score)

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from itertools import combinations_with_replacement, combinations
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, q = LI()
L = LIR(q)
ans = 0
for arr in combinations_with_replacement(range(1, m + 1), n):
    ret = 0
    for a, b, c, d in L:
        if arr[b - 1] - arr[a - 1] == c:
            ret += d
    ans = max(ans, ret)

print(ans)

Solution (Python):
import itertools

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())
    a[i] -= 1
    b[i] -= 1

ans = 0
for x in itertools.combinations_with_replacement(range(1, M+1), N):
    
    count = 0
    for i in range(Q):
        if x[b[i]] - x[a[i]] == c[i]:
            count += d[i]
    ans = max(ans,count)

print(ans)

Solution (Python):
def dfs(A):
  global ans
  if len(A)==N: 
    now=0
    for i in l:
      if A[i[1]-1]-A[i[0]-1]==i[2]:
        now+=i[3]
    ans=max(ans,now)
    return A

  A.append(A[-1])
  while A[-1]<=M:
    dfs(A[:])
    A[-1]+=1
    
  
N,M,Q=[int(x) for x in input().rstrip().split()]
A=[1]
l=[]
ans=0
for i in range(Q):
  abcd=[int(x) for x in input().rstrip().split()]
  l.append(abcd)
dfs(A)
print(ans)

Solution (Python):
def main():
    n, m, q = map(int, input().split())
    l = []
    for i in range(q):
        l1, l2, l3, l4 = map(int, input().split())
        l.append([l1, l2, l3, l4])
    B = []
    for a in range(1, m + 1):
        for b in range(a, m + 1):
            for c in range(b, m + 1):
                for d in range(c, m + 1):
                    for e in range(d, m + 1):
                        for f in range(e, m + 1):
                            for g in range(f, m + 1):
                                for h in range(g, m + 1):
                                    for i in range(h, m + 1):
                                        for j in range(i, m + 1):
                                            L = [a, b, c, d, e, f, g, h, i, j]
                                            A = []
                                            for I in range(n):
                                                A.append(L[I])
                                            C = 0
                                            for k in range(q):
                                                if A[l[k][1] - 1] - A[l[k][0] - 1] == l[k][2]:
                                                    C += l[k][3]
                                            B.append(C)
    print(max(B))
    
main()

Solution (Python):
import itertools
import numpy as np
n,m,q = map(int, input().split())
array = np.array(list(itertools.combinations_with_replacement(range(1,m+1),n)))
result = np.zeros((len(array)), dtype="int")
for i in range(q):
    temp = 0
    a,b,c,d = map(int, input().split())
    where = array[:,b-1] - array[:,a-1] == c
    result[where] += d
print(max(result))

Solution (Python):
import itertools
import numpy as np

def main():
    ans = 0
    n,m,q = map(int, input().split())
    qs = [list(map(int, input().split())) for _ in range(q)]
    l = list(itertools.combinations_with_replacement(range(1, m+1), n))
    for t in l:
        temp = 0
        for a,b,c,d in qs:
            if t[b-1] - t[a-1] == c:
                temp += d
        ans = max(ans, temp)
                
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n, m, q = map(int, input().split())
l = []
for i in range(q):
    l1, l2, l3, l4 = map(int, input().split())
    l.append([l1, l2, l3, l4])
B = []
for a in range(1, m + 1):
    for b in range(a, m + 1):
        for c in range(b, m + 1):
            for d in range(c, m + 1):
                for e in range(d, m + 1):
                    for f in range(e, m + 1):
                        for g in range(f, m + 1):
                            for h in range(g, m + 1):
                                for i in range(h, m + 1):
                                    for j in range(i, m + 1):
                                        L = [a, b, c, d, e, f, g, h, i, j]
                                        A = []
                                        for I in range(n):
                                            A.append(L[I])
                                        C = 0
                                        for k in range(q):
                                            if A[l[k][1] - 1] - A[l[k][0] - 1] == l[k][2]:
                                                C += l[k][3]
                                        B.append(C)
print(max(B))

Solution (Python):
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())

ans_list=[]  
from copy import deepcopy
def dfs(x,M,N,ans):
  if len(ans)<=N:
    ans.append(x)
    if len(ans)==N:
      ans_list.append(ans)
    else:
      for i in range(x,M+1):
        tmp=deepcopy(ans)
        dfs(i,M,N,tmp)   
      
q=dfs(1,M,N,[])

f=0
for A in ans_list:
  cnt=0
  for i in range(Q):
    if A[b[i]-1]-A[a[i]-1]==c[i]:
      cnt += d[i]
  f=max(f,cnt)
  
print(f)

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

import itertools
ans = 0

for a in itertools.combinations_with_replacement(range(1, m+1), n):
    score = 0
    for j in judge:
        if a[j[1]-1] - a[j[0]-1] == j[2]:
            score += j[3]
    ans = max(ans,score)

print(ans)

Solution (Python):
def main(k, s):
    if k == n:
        return sum(d * (s[b] - s[a] == c) for a, b, c, d in abcd)
    return max(main(k + 1, s + [ai]) for ai in range(s[-1], m + 1))

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    print(main(0, [1]))

Solution (Python):
import itertools

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


ans = 0
for l in itertools.combinations_with_replacement(range(1, m + 1), n):
    tmp_sum = 0
    for a, b, c, d in lst:
        if l[b - 1] - l[a - 1] == c:
            tmp_sum += d
    if ans < tmp_sum:
        ans = tmp_sum

print(ans)

Solution (Python):
def c():
    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())

    def dfs(lst, depth):
        score = 0
        if len(lst) < depth:
            start = 1 if len(lst) == 0 else lst[-1]
            for m in range(start, M+1):
                score = max(score, dfs(lst + [m], depth))
            return score

        else:
            for i in range(Q):
                score += d[i] if lst[b[i]-1] - lst[a[i]-1] == c[i] else 0
            return score

    A = []
    print(dfs(A, N))



if __name__ == "__main__":
    c()

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

BCD = [[] for _ in range(N)]
for _ in range(Q):
    a, b, c, d = map(int, input().split())
    BCD[a - 1].append((b - a, c, d))

def search(mi, A):
    if len(A) > N:
        return 0

    ret = 0
    for i in range(1, A[-1] + 1):
        ret = max(ret, search(i, A + (i,)))

    d = len(A)
    for b, c, d in BCD[N - d]:
        if A[-(b + 1)] - A[-1] == c:
            ret += d
    return ret

ans = 0
for i in range(1, M + 1):
    ans = max(ans, search(i, (i,)))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
n, m, q = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0


def dfs(u, A):
    global n, m, q, l, ans
    if len(A) == n:  
        score = 0
        for i in range(q):
            a, b, c, d = l[i]
            a, b,  = a - 1, b - 1
            if A[b] - A[a] == c:
                score += d
        ans = max(ans, score)
    else:  
        for i in range(u, m + 1):
            dfs(i, A + [i])


def main():
    dfs(1, [1])
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(500000)

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

def dfs(A: list):
    if len(A) == N:
        arr.append(A)
        return
    start = 1 if len(A) == 0 else A[-1]
    for i in range(start, M+1):
        dfs(A+[i])

dfs([])

ans = 0
for A in arr:
    tmp = 0
    for a,b,c,d in abcd:
        if A[b-1] - A[a-1] == c:
            tmp += d
    if ans < tmp:
        ans = tmp
print(ans)

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

Solution (Python):
def comb(k, s, r):
    if k == n:
        r.append(s[1:])
        return
    for ai in range(s[-1], m + 1):
        comb(k + 1, s + [ai], r)
    return r

def main():
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    s = 0
    for p in comb(0, [1], []):
        t = 0
        for a, b, c, d in abcd:
            t += d * (p[b - 1] - p[a - 1] == c)
        s = max(s, t)
    print(s)

if __name__ == '__main__':
    n, m, q = map(int, input().split())
    main()

Solution (Python):
import itertools

n, m, q = map(int, input().split())
lst = []
for _ in range(q):
    lst_tmp = [int(i) for i in input().split()]
    lst.append(lst_tmp)

ans = 0

for l in itertools.combinations_with_replacement(range(1, m + 1), n):
    tmp_sum = 0
    for a, b, c, d in lst:
        if l[b - 1] - l[a - 1] == c:
            tmp_sum += d
    if ans < tmp_sum:
        ans = tmp_sum

print(ans)

Solution (Python):
def comb(k, n, m, s, r):
    if k == n:
        r.append(s[1:])
        return
    for ai in range(s[-1], m + 1):
        comb(k + 1, n, m, s + [ai], r)
    return r

def main():
    n, m, q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(q)]
    s = 0
    for p in comb(0, n, m, [1], []):
        t = 0
        for a, b, c, d in abcd:
            t += d * (p[b - 1] - p[a - 1] == c)
        s = max(s, t)
    print(s)

if __name__ == '__main__':
    main()

Solution (Python):
n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
p=[]
import sys
sys.setrecursionlimit(10**6)
def dfs(x):
	if len(x)==n:
		p.append(x)
	else:
		for i in range(m-x[-1]+1):
			dfs(x+[x[-1]+i])
dfs([1])


for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

Solution (Python):
n,m,q = map(int,input().split())
arr = [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):
                                        tmp = 0
                                        arrs = [0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        for a, b, c, d in arr:
                                            if arrs[b] - arrs[a] == 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):
  aa,bb,cc,dd=map(int,input().split())
  a.append(aa-1)
  b.append(bb-1)
  c.append(cc)
  d.append(dd)
l=[int(i) for i in range(1,m+1)]
from itertools import combinations_with_replacement
ans=0
for ll in list(combinations_with_replacement(l,n)):
  t=0
  for i in range(q):
    if ll[b[i]]-ll[a[i]]==c[i]:
      t+=d[i]
  ans=max(ans,t)
print(ans)

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

Solution (Python):



N, M, Q = map(int, input().split())
q_list = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    q_list.append([a, b, c, d])


max_ans = 0


def dfs_score(a_list, p, n, max_ans):
    if p==N:
        tmp_score = 0
        for q in q_list:
            if a_list[q[1]-1]-a_list[q[0]-1]==q[2]:
                tmp_score += q[3]
        max_ans = max(max_ans, tmp_score)
    else:
        for i in range(n, M+1):
            a_list[p] = i
            max_ans = dfs_score(a_list, p+1, i, max_ans)
    return max_ans


a_list = [0]*N
max_ans = dfs_score(a_list, 0, 1, max_ans)
print(max_ans)