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 = list(map(int,input().split()))
Q = [list(map(int,input().split())) for i in range(N[2])]




from itertools import combinations_with_replacement as comb_rplc

C = 0
for seq in comb_rplc(range(1, N[1]+1), N[0]):
    S = 0
    for i in range(N[2]):
        if seq[Q[i][1]-1]-seq[Q[i][0]-1] == Q[i][2]:
            S += Q[i][3]
    if S > C:
        C = S
print(C)

Solution (Python):
import itertools
N, M, Q = map(int, input().split())
max = 0
s = ''
for i in range(M):
    s += str(i)
l = list(itertools.combinations_with_replacement(s, N))
m = [list(map(int, input().split())) for i in range(Q)]
for x in l:
    count = 0
    for y in m:
        if int(x[y[1] - 1]) - int(x[y[0] - 1]) == y[2]:
            count += y[3]
    if count > max:
        max = count
print(max)

Solution (Python):
from itertools import combinations_with_replacement as H
N, M, Q = map(int, input().split())
ans = 0
query = [list(map(int, input().split())) for _ in range(Q)]

for A in H(list(range(1, M+1)), N):
    acc = 0
    for j in range(Q):
        a, b, c, d = query[j]
        if A[b - 1] - A[a - 1] == c:
            acc += d
    ans = max(ans, acc)
print(ans)

Solution (Python):
def dfs(A):
    if len(A) == n+1:
        p = 0
        global ans
        for i in range(q):
            if A[b[i]]-A[a[i]] == c[i]:
                p += d[i]
        if p > ans:
            ans = p
        return
    num = A[-1]
    while num <= m:
        dfs(A[:]+[num])
        num += 1


if __name__ == "__main__":
    n, m, q = map(int, input().split())
    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())
    ans = 0
    dfs([1])
    print(ans)

Solution (Python):
from itertools import combinations_with_replacement as cwr
n,m,q=map(int,input().split())
abcd = [list(map(int,input().split())) for _ in range(q)]

def calscore(A):
    score = 0
    for a,b,c,d in abcd:
        if A[b-1] -A[a-1] ==c:
            score += d
    return score

ans =0
for A in cwr(range(1,m+1),n):
    ans = max(ans, calscore(A))
print(ans)

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

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

ans = 0
for l in itertools.combinations_with_replacement(range(1, m + 1), n):
    tmp = 0
    for i in range(q):
        a, b, c, d = abcd[i]
        if l[b - 1] - l[a - 1] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Solution (Python):
from itertools import combinations_with_replacement

n,m,q=map(int,input().split())
A=list(range(1,m+1))
s=(list(combinations_with_replacement(A,n)))
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 i in s:
    total=0
    for j in range(q):
        if i[b[j]-1]-i[a[j]-1]==c[j]:
            total+=d[j]
    ans=max(ans,total)
print(ans)

Solution (Python):
from itertools import combinations_with_replacement

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


def cal_score(A):
    score = 0
    for a, b, c, d in abcds:
        if A[b-1] - A[a-1] == c:
            score += d
    return score


ans = 0
for A in combinations_with_replacement([i for i in range(M)], N):
    ans = max(ans, cal_score(A))
print(ans)

Solution (Python):
from itertools import combinations_with_replacement as cwr

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

def calc_score(A):
  score = 0
  for a, b, c, d in abcd:
    if A[b-1] - A[a-1] == c:
      score += d
  return score

ans = 0
for A in cwr([i for i in range(1, M+1)], N):
  ans = max(ans, calc_score(A))

print(ans)

Solution (Python):
import itertools

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

com_list = list(itertools.combinations_with_replacement(range(M), N))
ans = 0
for com in com_list:
    tmp = 0
    for abcd in abcd_list:
        if (com[abcd[1]-1] - com[abcd[0]-1]) == abcd[2]:
            tmp += abcd[3]
    ans = max(ans, tmp)
print(ans)

Solution (Python):


import sys
stdin = sys.stdin
from itertools import combinations_with_replacement

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n, m, q = na()
    matrix = list()
    for i in range(q):
        matrix.append(na())
    l = list(combinations_with_replacement(range(1, m+1), n))
    ans = 0
    for li in l:
        res = 0
        for q in matrix:
            a, b, c, d = q
            if li[b-1] - li[a-1] == c:
                res += d
        ans = max(ans, res)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))



def solve():
    n, m, q = rl()
    Q = []
    for i in range(q):
        Q.append(rl())

    ways = [[i] for i in range(1, m + 1)]
    for i in range(n - 1):
        new_ways = []
        for way in ways:
            new_way = list(way)
            for j in range(way[-1], m + 1):
                new_ways.append(new_way + [j])
        ways = new_ways

    best = 0
    for way in ways:
        tot = 0
        for a, b, c, d in Q:
            if way[b - 1] - way[a - 1] == c:
                tot += d
        best = max(best, tot)

    print (best)







mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Solution (Python):
import itertools

N, M, Q = map(int, input().split())
q = [list(map(int, input().split())) for _ in range(Q)]
a = [0] * N
max_score = 0
for v in itertools.combinations(range(N + M - 1), N):
    tmp_score = 0
    for n in range(N):
        a[n] = v[n] + 1 - n
    for query in q:
        if (a[query[1] - 1] - a[query[0] - 1]) == query[2]:
            tmp_score += query[3]
    if max_score < tmp_score:
        max_score = tmp_score
print(max_score)

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

import itertools
A = [i for i in range(1,m+1)]
k = list(itertools.combinations_with_replacement(A, n))


ma = 0
for i in k:
    su = 0
    for n in s:
        if i[n[1]-1] - i[n[0]-1] == n[2]:
            su += n[3]
    ma = max(ma,su)

print(ma)

Solution (Python):

import itertools

(n, m, q), *r = [[*map(int, t.split())] for t in open(0)]
ans = 0
for i in list(itertools.combinations_with_replacement(range(1, m + 1), n)):
    sub = 0
    for a, b, c, d in r:
        sub += d * (i[b - 1] - i[a - 1] == c)
    ans = max(ans, sub)
print(ans)

Solution (Python):

import itertools

(n, m, q), *r = [[*map(int, t.split())] for t in open(0)]
ans = 0
for i in list(itertools.combinations_with_replacement(range(1, m + 1), n)):
    sub = 0
    for a, b, c, d in r:
        sub += d * (i[b - 1] - i[a - 1] == c)
    ans = max(ans, sub)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')


from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations




def solve():
    N, M, Q = MI()
    D = [[] for _ in range(Q)]
    for i in range(Q):
        a, b, c, d = MI()
        a -= 1
        b -= 1
        D[i] = [a, b, c, d]

    ans = 0
    for K in comb_w(range(1, M+1), N):
        score = 0
        for q in range(Q):
            a, b, c, d = D[q]
            if K[b] - K[a] == c:
                score = score + d
        ans = max(ans, score)

    print(ans)


if __name__ == '__main__':
    solve()

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

t = [1]*(n+1)
ans = 0
while t[0] == 1:
    s = 0
    for i in range(q):
        if t[l[i][1]]-t[l[i][0]] == l[i][2]:
            s += l[i][3]
    ans = max(ans, s)
    k = n
    while t[k] == m and k >= 1:
        k -= 1
    t[k] += 1
    for i in range(k+1, n+1):
        t[i] = t[i-1]

print(ans)

Solution (Python):
from collections import deque

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

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

def calc(li):
    score = 0
    for a, b, c, d in l:
        if li[b-1]-li[a-1] == c:
            score += d
    return score

que = deque([[i] for i in range(1, M+1)])
ans = 0

while que:
    li = que.popleft()
    if len(li) == N:
        score = calc(li)
        ans = max(ans, score)
    else:
        for i in range(li[-1],M+1):
            next = li + [i]
            que.append(next)
    

print(ans)

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

Solution (Python):
import itertools
N, M, Q = [int(x) for x in input().split(" ")]

conditions = [[int(x) for x in input().split(" ")] for _ in range(Q)]

def add(l, N):
    if len(l) == 0:
        b = 1
    else:
        b = l[-1]
    ans = []
    for i in range(b, N+1):
        ans.append(l + [i])
    return ans

L = [[]]
for _ in range(N):
    nex = []
    for l in L:
        nex.extend(add(l, M))
    L = nex

smax = 0
for l in L:
    s = 0
    for c in conditions:
        if l[c[1]-1] - l[c[0]-1] == c[2]:
            s += c[3]
    if s > smax:
        smax = s
print(smax)

Solution (Python):
import itertools
N, M, Q = [int(x) for x in input().split(" ")]

conditions = [[int(x) for x in input().split(" ")] for _ in range(Q)]

def add(l, N):
    if len(l) == 0:
        b = 1
    else:
        b = l[-1]
    ans = []
    for i in range(b, N+1):
        ans.append(l + [i])
    return ans

L = [[]]
for _ in range(N):
    nex = []
    for l in L:
        nex.extend(add(l, M))
    L = nex

smax = 0
for l in L:
    s = 0
    for c in conditions:
        if l[c[1]-1] - l[c[0]-1] == c[2]:
            s += c[3]
    if s > smax:
        smax = s
print(smax)

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())

def score(l):
    res = 0
    for i in range(q):
        temp = l[b[i] - 1] - l[a[i] - 1]
        if temp == c[i]:res += d[i]

    return res

def dfs(l):
    global ans
    if len(l) == n:
        ans = max(ans, score(l))
        return 

    if l:
        temp = l[-1]
    else:
        temp = 1
    for v in range(temp, m + 1):
        l.append(v)
        dfs(l)
        l.pop()

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

Solution (Python):
import sys
from itertools import combinations_with_replacement

input = sys.stdin.readline


def main():
    N, M, Q = map(int, input().split())
    abcd = [None] * Q
    for i in range(Q):
        abcd[i] = list(map(int, input().split()))
        abcd[i][0] -= 1
        abcd[i][1] -= 1

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]



def ascending(N, M):
    
    A = [0] * N
    yield A
    while True:
        
        k = None
        for i in reversed(range(N)):
            if A[i] < M - 1:
                k = i
                break
        if k is not None:
            A[k] += 1
            for j in range(k + 1, N):
                A[j] = A[k]
        else:
            return
        yield A


INF = float("inf")
MOD = 10**9 + 7


def main():
    n, m, q = MAP()
    abcd = ZIP(q)

    def point(A):
        tot = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                tot += d
        return tot

    
    ans = 0
    for a in ascending(n, m):         
        p = point(a)
        
        if ans <= p:
            ans = p
    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def main():
    n, m, q = MAP()
    abcd = ZIP(q)

    def ascending(X):
        for i in range(1, n):
            if A[i - 1] > A[i]:
                return False
        return True

    def point(A):
        tot = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                tot += d
        return tot

    def forward(A):
        
        k = None
        for i in reversed(range(n)):
            if A[i] < m:
                k = i
                break
        if k is not None:
            A[k] += 1
            for j in range(k + 1, n):
                A[j] = A[k]
        else:
            A[0] = INF

    
    A = [1] * n
    ans = 0
    while ascending(A):         
        
        p = point(A)
        if ans <= p:
            ans = p
        forward(A)
    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

num=1
seed = [[i] for i in range(1,m+1)]
while num!=n:
  num+=1
  tmp_list = []
  while seed:
    tmp = seed.pop()
    for i in range(tmp[-1],m+1):
      tmp_list.append(tmp+[i])
  seed = tmp_list.copy()

max_score = 0
visited = set()
for arr in seed:
  score = 0
  for arr_2 in list_:
    if arr[arr_2[1]-1] - arr[arr_2[0]-1] == arr_2[2]:
      score+=arr_2[3]
      max_score = max(max_score, score)
print(max_score)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations_with_replacement, compress
import sys
import math
import bisect
 
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
 
 
def I(): return int(sys.stdin.readline())
 
 
def LS(): return [list(x) for x in sys.stdin.readline().split()]
 
 
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
 
 
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)]
 
 
sys.setrecursionlimit(1000000)
 
 
def main():
    N, M, Q = LI()
    abcd = [LI() for _ in range(Q)]
    ans = 0
 
    for A in combinations_with_replacement(range(1, M + 1), N):
        tmp = 0
        for (a, b, c, d) in abcd:
            tmp += d if (A[b-1] - A[a-1] == c) else 0
        ans = max(ans, tmp)
    print(ans)
 
 
main()

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations_with_replacement, compress
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


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)]


sys.setrecursionlimit(1000000)


def main():
    N, M, Q = LI()
    abcd = [LI() for _ in range(Q)]
    ans = 0

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


main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


n,m,q = inpl()
abc = [inpl() for _ in range(q)]
q = deque()
q.append([1])
res = 0
while q:
    now = q.popleft()
    if len(now) == n+1:
        
        ans = 0
        for i,x in enumerate(abc):
            a,b,c,d = x
            if now[b] - now[a] == c:
                ans += d
        res = max(ans, res)
        continue
    for i in range(now[-1], m+1):
        q.append(now + [i])
print(res)

Solution (Python):
from itertools import combinations_with_replacement as combi

N, M, Q = map(int, input().split())
a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q
l = [i+1 for i in range(M)]
point = 0

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

for v in combi(l, N):
    tmp = 0
    for j in range(Q):
        if v[b[j]-1] - v[a[j]-1] == c[j]:
            tmp += d[j]
    point = max(point, tmp)

print(point)

Solution (Python):
from itertools import combinations_with_replacement as C

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_ = list(range(1, M + 1))
A_ = list(C(A_, N))

ans = 0
ans_ = 0
for A in A_:
    ans_ = 0
    for i in range(Q):
        if A[b[i] - 1] - A[a[i] - 1] == c[i]:
            ans_ += d[i]
    if ans < ans_:
        ans = ans_

print(ans)

Solution (Python):
def dfs(A):
    if len(A) == n+1:
        p = 0
        for i in range(q):
            if A[b[i]]-A[a[i]] == c[i]:
                p += d[i]
        global ans
        if p > ans:
            ans = p
        return
    num = A[-1]
    global m
    while num <= m:
        dfs(A[:]+[num])
        num += 1
                    

if __name__ == "__main__":
    n, m, q = map(int, input().split())
    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())
    ans = 0
    dfs([1])
    print(ans)

Solution (Python):
from itertools import combinations_with_replacement as comb_rplc

N, M, Q = list(map(int, input().split()))
A = []
B = []
C = []
D = []
for i in range(Q):
    in1, in2, in3, in4 = list(map(int,input().split()))
    A.append(in1 - 1)
    B.append(in2 - 1)
    C.append(in3)
    D.append(in4)
    
ans = 0
for seq in comb_rplc(range(1, M + 1), N):
    temp = 0
    for i in range(Q):
        if seq[B[i]] - seq[A[i]] == C[i]:
            temp += D[i]
        ans = max(ans, temp)
print(ans)

Solution (Python):
from itertools import combinations_with_replacement as comb_rplc
n,m,q = map(int, input().split())
arr = []

for i in range(q):
  arr.append(list(map(int, input().split())))
  
score_max = 0
for seq in comb_rplc(range(1, (m+1)), n):
  score = 0
  
  for a,b,c,d in arr:
    if seq[b-1]-seq[a-1] == c:
      score += d
      
  if score > score_max:
    score_max = score
    
print(score_max)

Solution (Python):
import itertools

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())

aa = [i for i in range(1, m+1)]
maxv = -1
for i in itertools.combinations_with_replacement(aa, n):
    cnt = 0
    for j in range(q):
        if i[b[j]-1] - i[a[j]-1] == c[j]:
            cnt += d[j]
    maxv = max(maxv, cnt)

print(maxv)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

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

l = []

for i in range(Q):
    a,b,c,d = map(int, input().split())
    l.append((a,b,c,d))

ans = 0
stack = [[1]]

while stack:
    a = stack.pop()
    if len(a) == N:
        score = 0
        for j in l:
            if a[j[1]-1] - a[j[0]-1] == j[2]:
                score += j[3]   
        ans = max(score, ans)
    else:
        for k in range(a[-1], M+1):
            s = a[:]
            s.append(k)
            stack.append(s)
print(ans)

Solution (Python):
from collections import deque
N, M, Q = map(int, input().split())
A = [list(map(int, input().split())) for i in range(Q)]

def calc(x):
    ans = 0
    for a, b, c, d in A:
        if int(x[b-1]) - int(x[a-1]) == c:
            ans += d
    return ans

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

print(ans)

Solution (Python):
from collections import deque
N, M, Q = map(int, input().split())
A = [list(map(int, input().split())) for i in range(Q)]

def calc(x): 
    ans = 0
    for a, b, c, d in A:
        if int(x[b-1]) - int(x[a-1]) == c:
            ans += d
    return ans

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

print(ans)

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

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

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

def dfs(a_l):
  if len(a_l)==n:
    global ans
    t_ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if (a_l[b]-a_l[a]==c):
        t_ans+=d
    ans=max(ans,t_ans)

    return

  a_last=a_l[-1]
  for i in range(a_last,m+1):
    dfs(a_l+[i])

ans=0
for i in range(1,m+1):
  dfs([i])

print(ans)

Solution (Python):
from collections import deque

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

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

ans = 0
que = deque()
for i in range(1, m + 1):
  que.append([i])
  
while que:
  seq = que.popleft()
  
  if len(seq) == n:
    score = calc(seq)
    ans = max(ans, score)
  else:
    for i in range(seq[-1], m + 1):
      seq_next = seq + [i]
      que.append(seq_next)
      
print(ans)

Solution (Python):
from itertools import combinations_with_replacement as comb_rplc

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

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

ans = 0

for seq in comb_rplc(range(1 , (m + 1)), n):
  score = 0
  
  for a, b, c, d in req:
    if seq[b - 1] - seq[a - 1] == c:
      score += d
  
  ans = max(ans, score)
  
print(ans)

Solution (Python):
import itertools


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

elem = [i for i in range(1, m+1)]


candidates = list(itertools.combinations_with_replacement(elem, n))

dsummax = 0
for cand in candidates:
    dsum = 0
    for i in range(q):
        if cand[pairs[i][1]-1]-cand[pairs[i][0]-1] == pairs[i][2]:
            dsum += pairs[i][3]
    if dsummax < dsum:
        dsummax = dsum

print(dsummax)

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):
  a1,b1,c1,d1 = map(int,input().split())
  a[i] = a1
  b[i] = b1
  c[i] = c1
  d[i] = d1

x = itertools.combinations_with_replacement(range(1,m+1),n)
tmp = 0
ans = 0
for xi in x:
  tmp = 0

  for i in range(q):
    if xi[b[i]-1] - xi[a[i]-1] == c[i]:
      tmp += d[i]
  ans = max(ans,tmp)

print(ans)

Solution (Python):
import itertools

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

A=[]
for i in range(Q):
    A.append(list(map(int,input().split())))
    A[i][0] -= 1
    A[i][1] -= 1

score = 0
max = 0

for iter in itertools.combinations_with_replacement(range(1,M+1),N):

    score = 0
    for i in range(Q):
        if iter[A[i][1]] - iter[A[i][0]] == A[i][2]:
            score += A[i][3]

    if max < score:
        max = score


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())
    
import itertools
A = list(itertools.combinations_with_replacement(range(1,M+1), N))
ans = 0
for j in A:
    temp = 0
    for i in range(Q):
        if j[b[i]-1]-j[a[i]-1] == c[i]:
            temp += d[i]
    ans = max(ans,temp)
print(ans)

Solution (Python):
import itertools

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


ans = 0
for iter in itertools.combinations_with_replacement(range(1, m+1), n):
    score = 0
    for i in range(q):
        a, b, c, d = L[i]
        if iter[b-1]-iter[a-1]==c:
            score += d

    ans = max(ans, score)

print(ans)

Solution (Python):
from itertools import combinations_with_replacement

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

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

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

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

import itertools as itl
gl=list(range(1, m+1))  

ans=0
for v in itl.combinations_with_replacement(gl, n): 
  check=0
  for i in range(q):
    if v[l[i][1]-1]-v[l[i][0]-1]==l[i][2]:
      check+=l[i][3]
  ans=max(check, ans)
print(ans)

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

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

ans = 0
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):
                                        tmp = 0
                                        MM = [a, b, c, d, e, f, g, h, i, j][:N]
                                        for ai, bi, ci, di in A:
                                            if MM[bi-1]-MM[ai-1] == ci:
                                                tmp += di
                                        ans = max(ans, tmp)
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, M, Q = getNM()
query = [getList() for i in range(Q)]


def counter(array):
    cnt = 0
    for i in range(Q):
        A_b = array[query[i][1] - 1]
        A_a = array[query[i][0] - 1]
        c = query[i][2]
        point = query[i][3]

        if A_b - A_a == c:
            cnt += point
    return cnt

ans = 0

def rep_comb_pow_2(i, array):
    global ans
    if i == N:
        opt = counter(array)
        ans = max(ans, opt)
        return

    
    last = 1
    if len(array) > 0:
        last = array[-1]

    for j in range(last, M + 1):
        new_array = array + [j]
        rep_comb_pow_2(i + 1, new_array)


rep_comb_pow_2(0, [])

print(ans)

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

Solution (Python):

from itertools import combinations
N, M, Q = map(int, input().split())
ls = []
for i in range(Q):
    ls.append([int(j) for j in input().split()])
V = [[] for i in range(N+1)]
for i in range(1, M+1):
    V[1].append([i])

for i in range(1, N):
    for v in V[i]:
        b = v[-1]
        for x in range(b, M+1):
            V[i+1].append(v + [x])
ans = 0
for x in V[-1]:
    cur = 0
    for z in ls:
        if x[z[1]-1] - x[z[0]-1] == z[2]:
            cur += z[3]
    ans = max(ans, cur)
print(ans)