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

import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

def check(l,c):
    if l[c[1]-1] - l[c[0]-1] == c[2]:
        return True
    else:
        return False

n,m,q = LI()
li = LLI(q)
num = [i for i in range(1,m+1)]
a =  list(itertools.combinations_with_replacement(num, n))
ans = 0
ans_li = []
for suuretsu in a:
    ans = 0 
    for ch in li: 
        if check(suuretsu,ch):
            ans += ch[3]
    ans_li.append(ans)
print(max(ans_li))

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n,m,q = map(int,input().split())
E = [list(map(int,input().split())) for i in range(q)]
def dfs(l,string):
  if l == n:
    global ans
    ans = max(ans,check(string));return
  for i in range(int(string[-1]),m+1):
    dfs(l+1,(string+[str(i)]).copy())

def check(string):
  global count
  count += 1
  re = 0
  for a,b,c,d in E:
    if int(string[b])-int(string[a]) == c:
      re += d
  
  return re
dfs(0,[1])
print(ans)

Solution (Python):



def main():
    from itertools import combinations_with_replacement
    import numpy as np

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

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

    temp_As = np.array(
        tuple(combinations_with_replacement(
            iterable=range(1, M + 1),
            r=N
        )), dtype=np.int32
    )

    scores = np.zeros(len(temp_As), dtype=np.int32)
    for a, b, c, d in abcd:
        cond = temp_As[:, b] - temp_As[:, a] == c
        scores += d * cond

    print(scores.max())


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations_with_replacement

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

L = [i for i in range(1, M+1)]

iterations = combinations_with_replacement(L, N)

max_score = 0
for v in iterations:
    score = 0
    for i in range(Q):
        if v[b[i]-1] -  v[a[i]-1] == c[i]:
            score += d[i]
    if score > max_score:
        max_score = score

print(max_score)

Solution (Python):
def dfs(A):
    global ans
    if len(A) == N:
        score = 0
        for a, b, c, d in buff:
            if A[b - 1] - A[a - 1] == c:
                score += d
        ans = max(ans, score)
        return

    A.append(A[-1])
    while A[-1] <= M:
        dfs(A[:])
        A[-1] += 1


N, M, Q = map(int, input().split())
buff = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
dfs([1])
print(ans)

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

    com = [int(x) for x in range(1, m+1)]
    ans = 0
    for i in combinations_with_replacement(com, n-1):
        cur = list(i)
        A = [1] + cur
        tot = 0
        for k in range(q):
            a, b, c, d = l[k]
            if A[b-1] - A[a-1] == c:
                tot += d
        ans = max(ans, tot)
    
    return ans


print(solve())

Solution (Python):
def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, M, Q = [int(x) for x in input().strip().split()]
    abcd = [0] * Q
    for q in range(Q):
        abcd[q] = [int(x) for x in input().strip().split()]

    abcd.sort(key=lambda x:(x[0],x[1]))
    vecs = []

    def makevecs(n, vecs, A):
        if n == N:
            vecs.append(A)
            return None
        for b in range(A[-1], M+1):
            makevecs(n+1, vecs, A+[b])
        return None
        
    makevecs(1, vecs, [1])
    ans = 0
    for vec in vecs:
        ans_ = 0
        for q in range(Q):
            a, b, c, d = abcd[q]
            if vec[b-1] - vec[a-1] == c:
                ans_ += d
        
        ans = max(ans, ans_)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(q)]
ls = [1]
ans=0
def dfs(n,m,i,ls,abcd):
    global ans
    temp=0
    if len(ls)==n:
        for j in abcd:
            if ls[j[1]-1] - ls[j[0]-1] == j[2]:
                temp+=j[3]
        ans=max(ans,temp)
    else:
        for j in range(i,m+1):
            dfs(n,m,j,ls+[j],abcd)
dfs(n,m,1,ls,abcd)
print(ans)

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

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

lst = [list() for _ in range(N + 1)]

for a, b, c, d in X:
    lst[b].append((a, c, d))


class Test:
    def __init__(self):
        self.max_ = 0

    def helper(self, idx, cnt, stack, tmp):
        if cnt == N + 1:
            self.max_ = max(self.max_, tmp)
            return

        for s, t, u in lst[cnt]:
            if stack[cnt - 1] - stack[s - 1] == t:
                tmp += u

        for i in range(idx, M + 1):
            stack.append(i)
            self.helper(i, cnt + 1, stack, tmp)
            stack.pop()


t = Test()
t.helper(1, 0, [], 0)

print(t.max_)

Solution (Python):
import itertools

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

for _ in range(q):
    con.append(list(map(int, input().split())))

A_li = list(itertools.combinations_with_replacement(range(1,m+1),n))

for A in A_li:
    now_score = 0
    for a,b,c,d in con:
        a-=1
        b-=1
        if A[b]-A[a] == c:
            now_score += d
    ans = max(ans, now_score)

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):
import itertools
n,m,q = map(int,input().split())
target = [list(map(int,input().split())) for _ in range(q)]
ans = 0
for A in itertools.combinations_with_replacement(range(1,m+1),n):
  count = sum([abcd[3] for abcd in target if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]])
  ans = max(ans,count)
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())
ans = 0
for A in itertools.combinations_with_replacement(range(m), n):
  tmp = 0
  for i in range(q):
    if A[b[i]-1] - A[a[i]-1] == c[i]:
      tmp += d[i]
  ans = max(ans, tmp)
print(ans)

Solution (Python):


import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, M, Q = LI()
ABCD = LRI(Q)

def calc(A):
    ret = 0

    for a, b, c, d in ABCD:
        if A[b] - A[a] == c:
            ret += d
    
    return ret

ans = 0
def dfs(A):
    global ans
    
    if len(A) == N+1:
        ans = max(ans, calc(A))
        return
    
    back = A[-1]
    while back <= M:
        dfs(A + [back])
        back += 1

dfs([1])

print(ans)

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

abcd = []
for i in range(q):
    abcd.append([int(i) for i in input().split()])

ans = 0
for a1 in range(1, 11):
    for a2 in range(a1, 11):
        for a3 in range(a2, 11):
            for a4 in range(a3, 11):
                for a5 in range(a4, 11):
                    for a6 in range(a5, 11):
                        for a7 in range(a6, 11):
                            for a8 in range(a7, 11):
                                for a9 in range(a8, 11):
                                    for a10 in range(a9, 11):
                                        
                                        A = [0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10]
                                        ans_ = 0
                                        if max(A) <= m:
                                            for i in range(q):
                                                if A[abcd[i][1]] - A[abcd[i][0]] == abcd[i][2]:
                                                    ans_ += abcd[i][3]
                                        ans = max(ans_, ans)

print(ans)

Solution (Python):
import itertools

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

Solution (Python):
import copy


def dfs(A):
    global ans
    if len(A) == N:
        score = 0
        for a, b, c, d in buff:
            if A[b - 1] - A[a - 1] == c:
                score += d
        ans = max(ans, score)
        return

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


N, M, Q = map(int, input().split())
buff = [list(map(int, input().split())) for _ in range(Q)]
ans = 0
dfs([1])
print(ans)

Solution (Python):
from sys import stdin
import itertools
N,M,Q = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for i in range(Q):
    a,b,c,d = [int(x) for x in stdin.readline().rstrip().split()]
    data.append((a,b,c,d))
    
ite = []
def f(n,cnt):
    if cnt == N:
        ite.append(n)
        return
    for i in range(1,M+1):
        if n[-1] <= i:
            f(n+[i],cnt+1)
f([1],0)
ans = 0
for i in ite:
    tmp = 0
    for a,b,c,d in data:
        if i[b-1] - i[a-1] == c:
            tmp += d
    ans = max(ans,tmp)
    
print(ans)

Solution (Python):
import itertools

def c165(n, m, q, adli):

    ans = 0
    li = list(itertools.combinations_with_replacement(range(1,m+1), n))
    for i in li:
        count = 0
        for a, b, c, d in adli:
            if i[b-1] - i[a-1] == c:
                count += d
        ans = max(ans, count)

    return ans

def main():
    n, m, q = map(int, input().split())
    adli = [list(map(int, input().split()))for i in range(q)]
    print(c165(n, m, q, adli))

if __name__ == '__main__':
    main()

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

ans = 0

for A in itertools.combinations_with_replacement(range(1,M + 1),N):
  temp = 0
  for p in pair:
    if A[p[1]-1] - A[p[0]-1] == p[2]:
      temp += p[3]
      ans = max(ans,temp)
    
print(ans)

Solution (Python):
from itertools import combinations_with_replacement as cwd

N, M, Q = map(int, input().split())
A = list(cwd(range(1, M + 1), N))
ABCD = []

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

res = 0
for i in A:
    tmp = 0
    for j in ABCD:
        if i[j[1]] - i[j[0]] == j[2]:
            tmp += j[3]
    res = max(res, tmp)

print(res)

Solution (Python):
N, M, Q, *ABCD = map(int, open(0).read().split())

def solve(A):
    if len(A) == N:
        return sum(d for a, b, c, d in zip(*[iter(ABCD)] * 4) if A[b - 1] - A[a - 1] == c)

    return max(solve(A + [i]) for i in range(A[-1], M + 1))

print(solve([1]))

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

y = [1 for i in range(n)]

def f(index,li):
    if index == n:
        return eva(li)
    else:
        ret = 0
        t = 1
        if index>=1:
            t = li[index-1]
        for i in range (t,m+1):
            li[index]=i
            x = f(index+1,li)
            if ret < x:
                ret = x
        return ret
    
def eva(li):
    tmp = 0
    for k in range(q):
        a = lst[k][0]
        b = lst[k][1]
        c = lst[k][2]
        d = lst[k][3]
        if li[b-1]-li[a-1]==c:
            tmp = tmp + d
    return tmp
    
print(f(0,y))

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

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

Solution (Python):
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(q)]
ls = [1]
ans=0
def dfs(n,m,i,ls):
    global ans
    global abcd
    temp=0
    if len(ls)==n:
        for j in abcd:
            if ls[j[1]-1] - ls[j[0]-1] == j[2]:
                temp+=j[3]
        ans=max(ans,temp)
    else:
        for j in range(i,m+1):
            dfs(n,m,j,ls+[j])
dfs(n,m,1,ls)
print(ans)

Solution (Python):
n,m,q = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(q)]
ls = [1]
ans=0
def dfs(n,m,i,ls):
    global ans
    global abcd
    temp=0
    if len(ls)==n:
        for j in abcd:
            if ls[j[1]-1] - ls[j[0]-1] == j[2]:
                temp+=j[3]
        ans=max(ans,temp)
    else:
        for j in range(i,m+1):
            dfs(n,m,j,ls+[j])
dfs(n,m,1,ls)
print(ans)

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

temp = [[i] for i in range(M)]
lsts = []
while temp:
    q = temp.pop()
    if len(q) == N:
        lsts.append(q)
        continue
    for i in range(q[-1], M):
        q1 = q[:]
        q1.append(i)
        temp.append(q1)
lsts.sort()  
ans = []
for lst in lsts:
    cnt = 0
    for k in abcd:
        if lst[k[1]-1] - lst[k[0]-1] == k[2]:
            cnt += k[3]
    ans.append(cnt)
print(max(ans))

Solution (Python):
import itertools
n,m,q = map(int,input().split())
target = [list(map(int,input().split())) for _ in range(q)]
ans = 0

for A in itertools.combinations_with_replacement(range(1,m+1),n):
  count = 0
  for abcd in target:
    if A[abcd[1]-1] - A[abcd[0]-1] == abcd[2]:
      count += abcd[3]
  
  ans = max(ans,count)

print(ans)

Solution (Python):

import sys
import itertools

N,M,Q=map(int, sys.stdin.readline().split())
X=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

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

ans=float("-inf")
for L in LL:
    temp_ans=0
    for a,b,c,d in X:
        if L[b-1]-L[a-1]==c:
            temp_ans+=d
    ans=max(ans,temp_ans)
print ans

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N, M, Q = map(int, input().split())
a_list = [list(map(int, input().split())) for i in range(Q)]

temp_list = []

max_count = 0


def solve(i, j):
    global max_count
    if i == N:
        temp_count = 0

        for m in a_list:
            if j[m[1] - 1] - j[m[0] - 1] == m[2]:
                temp_count += m[3]
        if max_count < temp_count:
            max_count = temp_count

        return

    a = 0
    if len(j) > 0:
        a = j[-1]
    else:
        a = 1
    for k in range(a, M + 1):
        solve(i + 1, j + [k])


solve(0, [])
print(max_count)

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

def eval(a):
  score = 0
  for c in constraints:
    if a[c[1] - 1] - a[c[0] - 1] == c[2]:
      score += c[3]
  return score


def dfs(a, i):
  if i == n:
    return eval(a)
  score = 0
  for x in range(a[i - 1] if 0 < i else 1, m + 1):
    a[i] = x
    score = max(score, dfs(a, i + 1))
  return score

print(dfs([None] * n, 0))

Solution (Python):

import sys
import math
import numpy as np
import itertools


n,m,q = (int(i) for i in input().split())
answer = 0

e = [[int(i) for i in input().split()] for i in range(q)] 
a=[1]*10
for i1 in range(1,m+1):
    a[1] = i1
    for i2 in range(i1,m+1):
        a[2] = i2
        for i3 in range(i2,m+1):
            a[3] = i3
            for i4 in range(i3,m+1):
                a[4] = i4
                for i5 in range(i4,m+1):
                    a[5] = i5
                    for i6 in range(i5,m+1):
                        a[6] = i6
                        for i7 in range(i6,m+1):
                            a[7] = i7
                            for i8 in range(i7,m+1):
                                a[8] = i8
                                for i9 in range(i8,m+1):
                                    a[9] = i9
                                    t=0
                                    for i in range(q):
                                        if a[e[i][1]-1] - a[e[i][0]-1] == e[i][2]:
                                            t += e[i][3]
                                        answer = max(t,answer)

print(answer)

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

R=[range(i,m) for i in range(m)]
def dfs(d,s):
    global n,m,Q,ans
    if d==n:
        ans_=0
        for k in Q:
            a,b,c,e=k
            if int(s[b-1])-int(s[a-1])==c:
                ans_+=e
        ans=max(ans,ans_)
    else:
        l=int(s[-1])
        for i in R[l]:
            dfs(d+1,s+str(i))
for i in R[0]:
    dfs(1,str(i))

print(ans)

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

def gen_list(li, n, m):
    if len(li[0]) == n:
        return li
    
    res = []
    for d in li:
        base = [i for i in range(d[-1], m+1)]
        for x in base:
            tmp = d.copy()
            tmp.append(x)
            res.append(tmp)
    return gen_list(res, n, m)

base = [[i] for i in range(1, m+1)]
A_list = gen_list(base, n, m)
ans = 0
for A in A_list:
    tmp = 0
    for d in query:
        if A[d[1]-1] - A[d[0]-1] == d[2]:
            tmp += d[3]
        if tmp > ans:
            ans = tmp

print(ans)

Solution (Python):
import itertools


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

patterns = itertools.combinations_with_replacement(range(1, m+1), n)

candidates = []
for pattern in patterns:
    res = 0
    for a, b, c, d in queries:
        if int(pattern[b]) - int(pattern[a]) == c:
            res += d

    candidates.append(res)

print(max(candidates))

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


maxi = 0

l = []
for i in range(m):
	l.append(i)

for a in itertools.combinations_with_replacement(l, n):
	
	pnt = 0
	for i in range(q):
		

		if a[s[i][1]-1]-a[s[i][0]-1] == s[i][2]:
			
			
			pnt += s[i][3]
	
	if pnt >maxi:
		maxi = pnt
		
print(maxi)

Solution (Python):
N, M, Q = map(int, input().split())
L = []
for i in range(Q):
    L.append(list(map(int, input().split())))
 
def f(s):
    if len(s) == N:
        return [s]
    yy = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, M):
        yy.extend(f(s + str(i)))
    return yy
 
ans = 0
V = f('')
for s in V:
    A = [int(c) + 1 for c in s]
    t = 0
    for a, b, c, d in L:
        if A[b - 1] - A[a - 1] == c:
            t += d
    ans = max(ans, t)
print(ans)

Solution (Python):
from collections import deque

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

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


def A_generator():
    q = deque()
    q.append([1])
    while len(q) > 0:
        a = q.pop()
        if len(a) < N + 1:
            for i in range(a[-1], M + 1):
                q.append(a + [i])
        else:
            yield a


ans = 0

for A in A_generator():
    point_sum = 0
    for p in point:
       if A[p[1]] - A[p[0]] == p[2]:
            point_sum += p[3]

    ans = max(ans, point_sum)

print(ans)

Solution (Python):
from collections import deque

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

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


def A_generator():
    q = deque()
    q.append([1])
    while len(q) > 0:
        a = q.pop()
        if len(a) < N + 1:
            for i in range(a[-1], M + 1):
                q.append(a + [i])
        else:
            yield a


ans = 0

for A in A_generator():
    point_sum = 0
    for p in point:
       if A[p[1]] - A[p[0]] == p[2]:
            point_sum += p[3]

    ans = max(ans, point_sum)

print(ans)

Solution (Python):
N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == N:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

    return max(solve(A + [i]) for i in range(A[-1], M + 1))

print(solve([1]))

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

a_l = [1] * n
ans = 0
while True:
    ans_tmp = 0
    for a, b, c, d in abcd:
        if a_l[b-1] - a_l[a-1] == c:
            ans_tmp += d
    ans = max(ans,ans_tmp)
    if a_l == [m]*n:
        break
    for i in range(1,n+1):
        a_l[-i] += 1
        if a_l[-i] == m+1:
            a_l[-i] = 1
            continue
        else:
            break
    for i in range(1,n):
        while a_l[i-1] > a_l[i]:
            a_l[i] += 1

print(ans)

Solution (Python):
def main():
    from itertools import combinations_with_replacement
    import sys
    input = sys.stdin.buffer.readline
    N, M, Q = (int(i) for i in input().split())
    T = [[int(i) for i in input().split()] for j in range(Q)]
    ans = 0
    for C in combinations_with_replacement(range(1, M+1), N):
        A = sorted(C)
        cur = 0
        for a, b, c, d in T:
            if A[b-1] - A[a-1] == c:
                cur += d
        ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]







N, M, Q = mi()
abcd = li2(Q)

a = '0' * N
m = str(M-1)
l = [a]

while True:
    i = N-1
    while i >= 0 and a[i] == m: 
        i -= 1
    if i == -1:
        break
    a = list(a) 
    num = str(int(a[i]) + 1) 
    a[i] = num
    if i != N-1:
        for j in range(i+1, N): 
            a[j] = num
    tmp = ''.join(a) 
    l.append(tmp)

ans = 0
for num in l:
    cnt = 0
    
    for i in range(Q):
        if int(num[abcd[i][1]-1]) - int(num[abcd[i][0]-1]) == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)

print(ans)

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

def dfs(A):
    global res
    if len(A) == N:
        tmp = 0
        for a, b, c, d in abcd:
            if A[b-1] - A[a-1] == c:
                tmp += d
        if tmp > res:
            res = tmp
        return

    if len(A) == 0:
        d = 1
    else:
        d = A[-1]

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

dfs([])
print(res)

Solution (Python):
from itertools import combinations_with_replacement
N,M,Q = (int(x) for x in input().split())
q = []
Max = 0
for i in range(Q):
    q.append(list(map(int, input().split())))
for x in combinations_with_replacement(range(1,M+1),N):
    temp = 0
    for y in q:
        if x[y[1]-1] - x[y[0]-1] == y[2]:
            temp += y[3]
    Max = max(temp,Max)
print(Max)

Solution (Python):
import itertools


def main():
    n,m,q = map(int,input().split())
    C_list = [list(map(int,input().split())) for _ in range(q)]

    A_list = itertools.combinations_with_replacement(range(1,m+1),n)
    ans = 0
    for A in A_list:
        tmp = 0
        for C in C_list:
            if A[C[1]-1]-A[C[0]-1] == C[2]:
                tmp += C[3]
        ans = max(ans,tmp)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import itertools
def main():
    
    readline=stdin.readline
    N,M,Q=map(int,readline().split())
    a=[]
    b=[]
    c=[]
    d=[]
    for i in range(Q):
        li=list(map(int,readline().split()))
        a.append(li[0])
        b.append(li[1])
        c.append(li[2])
        d.append(li[3])

    li_2=list(itertools.combinations_with_replacement(list(range(1,M+1)),N))
    
    max_res=0
    for i in range(len(li_2)):
        A=li_2[i]
        res=0
        for j in range(Q):
            if A[b[j]-1]-A[a[j]-1]==c[j]:
                res+=d[j]
        max_res=max(max_res,res)
    print(max_res)
if __name__=="__main__":
    main()

Solution (Python):
import itertools
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])
  
nums = list(itertools.combinations_with_replacement(range(1, M+1), N))
scores = []
for row in nums:
  score = 0
  i = 0
  while i < Q:
    if row[l[i][1]-1]-row[l[i][0]-1] == l[i][2]:
      score += l[i][3]
    i += 1
  scores.append(score)
  
print(max(scores))

Solution (Python):

import sys
from itertools import combinations_with_replacement

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M, Q = lr()
ABCD = [lr() for _ in range(Q)]
answer = 0
for x in combinations_with_replacement(range(1, M+1), N):
    temp = 0
    for a, b, c, d in ABCD:
        if x[b-1] - x[a-1] == c:
            temp += d
    if temp > answer:
        answer = temp

print(answer)

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


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


nums = [0] * (n + 1)

ans = dfs(nums, 0, 1)
print(ans)

Solution (Python):

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


def dfs(x,y,z,que):
    ret = 0
    if x == 0:
        for a,b,c,d in abcd:
            if que[b-1] - que[a-1]==c:
                ret+=d
        return ret
    for i in range(y,z+1):
        ret = max(ret,dfs(x-1,i,z,que + [i]))
    return ret

print(dfs(n,1,m,[]))

Solution (Python):
def main():
    from itertools import combinations_with_replacement

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

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

    ans = 0
    for temp_A in combinations_with_replacement(iterable=range(1, M + 1), r=N):
        
        t = 0
        for ai, bi, ci, di in conds:
            c = temp_A[bi] - temp_A[ai]
            if c == ci:
                t += di
        ans = max(ans, t)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque

N,M,Q=map(int, sys.stdin.readline().split())
X=[ map(int, sys.stdin.readline().split()) for _ in range(Q) ]

qq=deque()
for m in range(1,M+1):
    q=deque()
    q.append([m])
    while q:
        if N<len(q[0]):
            qq+=q
            break
        fro=q.popleft()
        last=fro[-1]
        for to in range(last,M+1):
            q.append(fro+[to])

ans=float("-inf")
for L in qq:
    temp_ans=0
    for a,b,c,d in X:
        if L[b-1]-L[a-1]==c:
            temp_ans+=d
    ans=max(ans,temp_ans)
print ans

Solution (Python):
import itertools
N, M, Q = map(int, input().split())
q_list = []
final_score = 0
for i in range(Q):
    q_list.append(list(map(int, input().split())))
for A in itertools.combinations_with_replacement(range(1,M+1), N):
    score = 0
    for q in q_list:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            score += q[3]
        final_score = max([final_score, score])
print(final_score)

Solution (Python):
import itertools

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

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

total = 0

l = [1,2,3,4,5,6,7,8,9,10,11]
for v in itertools.combinations_with_replacement(range(1, m+1), n):
    scores = []
    for a,b,c,d in nums:
        if v[b-1]-v[a-1] == c:
            scores.append(d)
        else:
            scores.append(0)
    if total < sum(scores):
        total = sum(scores)

print(total)