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 sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

from itertools import combinations_with_replacement as cwr
n,m,q=mp()
l=[lmp() for i in range(q)]
ans=0


for i in cwr(range(1,m+1),n):
    s=0
    for a,b,c,d in l:
        if i[b-1]-i[a-1]==c:
            s+=d
    ans=max(ans,s)
print(ans)

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

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

score = 0

a = [1] * n

def sco(a):
    scotem = 0
    for i in sets:
        if(a[i[1]-1] - a[i[0]-1] == i[2]):
            scotem += i[3]
    return scotem

flag = 1

while True:
    for i in range(n-1,-1,-1):
        flag = 0
        if(a[i] < m):
            flag = 1
            a[i] = a[i] + 1
            for j in range(n-1,i,-1):
                a[j] = a[i]
            if(sco(a) > score):
                score = sco(a)
            break
    if (flag == False):
        if(sco(a) > score):
            score = sco(a)
        break

print(str(score))

Solution (Python):



def solve():
    N, M, Q = map(int, input().split())
    abcd = [[int(i) for i in input().split()] for _ in range(Q)]

    
    def dfs(AA=[1], now_max=0):
        A = AA.copy()
        if len(A) == N + 1:
            new_max = 0
            for a, b, c, d in abcd:
                if A[b] - A[a] == c:
                    new_max += d
            now_max = max(now_max, new_max)
        else:
            for i in range(A[-1], M + 1):
                now_max = max(now_max, dfs(A + [i], now_max))
        return now_max

    print(dfs())


if __name__ == '__main__':
    solve()

Solution (Python):
N,M,Q = map(int,input().split())
ABCD = [tuple(map(int,input().split())) for i in range(Q)]
import itertools
ans = 0
for ptn in itertools.combinations_with_replacement(range(1,M+1), N):
    tmp = 0
    for a,b,c,d in ABCD:
        if ptn[b-1] - ptn[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())
X = [list(map(int, input().split())) for _ in range(Q)]
ans = 0

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


def dfs(arr):
    global ans
    if len(arr) == N:
        ans = max(ans, calc(arr))

    elif len(arr) == 0:
        for nx in range(1, M + 1):
            dfs(arr + [nx])

    else:
        for nx in range(arr[-1], M + 1):
            dfs(arr + [nx])


dfs([])
print(ans)

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

ans = 0
for pattern in combinations_with_replacement(range(1, M + 1), N):
    tmp_ans = 0
    pattern = list(pattern)
    for a, b, c, d in X:
        if pattern[b - 1] - pattern[a - 1] == c:
            tmp_ans += d
    ans = max(ans, tmp_ans)

print(ans)

Solution (Python):









import os
import sys


from itertools import combinations_with_replacement as crlp

def main():
    n,m,q = map(int,input().split())
    ans = 0
    a = []
    b = []
    c = []
    d = []
    for _ in range(q):
        a_,b_,c_,d_ = map(int,input().split())
        a.append(a_-1)
        b.append(b_-1)
        c.append(c_)
        d.append(d_)

    for seq in crlp(range(1,m+1),n):
        tmp = 0

        for i in range(q):
            if seq[b[i]]-seq[a[i]]==c[i]:
                tmp+=d[i]
        if ans<tmp:
            ans=tmp
    print(ans)

    


if __name__ == "__main__":
    main()

Solution (Python):
import itertools

n,m,q = map(int, input().split(" "))
a,b,c,d = [],[],[],[]
for i in range(q):
  inpu = input()
  a.append((int)(inpu.split(" ")[0]))
  b.append((int)(inpu.split(" ")[1]))
  c.append((int)(inpu.split(" ")[2]))
  d.append((int)(inpu.split(" ")[3]))

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

max = 0
for i in range(len(balls)):
  temp = 0
  for j in range(q):
    if balls[i][b[j] - 1] - balls[i][a[j] - 1] == c[j]:
      temp += d[j]
  if temp > max:
    max = temp
print(max)

Solution (Python):
import itertools

n,m,q = map(int, input().split(" "))
a,b,c,d = [],[],[],[]
for i in range(q):
  inpu = input()
  a.append((int)(inpu.split(" ")[0]))
  b.append((int)(inpu.split(" ")[1]))
  c.append((int)(inpu.split(" ")[2]))
  d.append((int)(inpu.split(" ")[3]))

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

max = 0
for i in range(len(balls)):
  temp = 0
  for j in range(q):
    if balls[i][b[j] - 1] - balls[i][a[j] - 1] == c[j]:
      temp += d[j]
  if temp > max:
    max = temp
print(max)

Solution (Python):
import bisect,collections,copy,heapq,itertools,math,numpy,string

import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M, Q = LI()
numlist = [LI() for _ in range(Q)]
part = 0
sum = 0
maxAs = 0
hist = []
stack = collections.deque()
stack.append([1,-1])	
while True:
	now = stack.pop()
	sumleft = now[0]
	histpos = now[1]
	hist.append(sumleft)
	histpos+=1
	if histpos == N:
		
		val = 0
		for l in numlist:
			if hist[l[1]-1]-hist[l[0]-1] == l[2]:
				val+=l[3]
		if val > maxAs:
			maxAs = val
		if not stack:
			break
		next = stack[len(stack)-1]
		hist = hist[0:next[1]+1]
		continue
	for i in range(0,M+1-sumleft):
		stack.append([sumleft+i, histpos])
print(maxAs)

Solution (Python):
def nex(x,m):
    for c in range(len(x)-1,-1,-1):
        if x[c]<m:
            x[c]+=1
            for d in range(c+1,len(x)):
                x[d]=x[c]
            return x
    return -1


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

s=0
a=[1]*n
while True:
    if a==-1:
        break
    p=0
    for i in range(q):
        if a[f[i][1]-1]-a[f[i][0]-1]==f[i][2]:
            p+=f[i][3]
    if p>s:
        s=p
    a=nex(a,m)
print(s)

Solution (Python):
from collections import deque

n, m, q = map(int,input().split())
q_list = []
point_list = []

for i in range(q):
    temp_list = list(map(int,input().split()))
    q_list.append(temp_list)

que = deque()
que.append([1,[]])
ans = 0
temp_list = []

while len(que) != 0:
    temp = que.pop()
    if len(temp[1]) != n:
        temp_list = []
        for i in range(temp[0], m+1):
            for j in temp[1]:
                temp_list.append(j)
            temp_list.append(i)
            que.append([i, temp_list])
            temp_list = []
    else:
        point = 0
        for q in q_list:
            if temp[1][q[1]-1] - temp[1][q[0]-1] == q[2]:
                point += q[3]
        if ans < point:
            ans = point

print(ans)

Solution (Python):
nmq = [int(x) for x in input().split()]

n = nmq[0]
m = nmq[1]
q = nmq[2]

lis = []

for i in range(0,q):
    lis.append([int(x) for x in input().split()])

def check(ar):
    total = 0
    for thing in lis:
        if ar[thing[1]] - ar[thing[0]] == thing[2]:
            total = total + thing[3]
    return total

def solve(pre,count):
    count = int(count)
    if count == n:
        return(check(pre))
    else:
        maxx = 0
        for i in range(pre[count],m+1):
            temp = solve(pre + [i], count+1)
            if temp > maxx:
                maxx = temp
        return(maxx)
    
print(solve([1],0))

Solution (Python):
import sys
sys.stdin.readline

def dfs(dmax, now):
    if len(now) == N:
        P.append(now)
        return
    for n in range(dmax, M+1):
        dfs(n, now+[n])

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

dfs(1, [])
ans = 0
for A in P:
    score = 0
    for a, b, c, d in ABCD:
        if A[b-1] - A[a-1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Solution (Python):
N,M,Q=map(int,input().split())
S=[]
for i in range(Q):
    S.append(list(map(int,input().split())))
try_lis=[]
def dfs(A):
    if len(A)==N:
        try_lis.append(A[::1])
        return   
    for v in range(1,M+1):
        if v>=A[-1]:
            A.append(v)
            dfs(A)
            A.pop()
dfs([1])
total=0
for one_case in try_lis:
    tmp=0
    for j in S:
        if one_case[j[1]-1]-one_case[j[0]-1]==j[2]:
            tmp+=j[3]
    total=max(total,tmp)
print(total)

Solution (Python):
N,M,Q=map(int,input().split())
S=[]
for i in range(Q):
    S.append(list(map(int,input().split())))
try_lis=[]
def dfs(A):
    if len(A)==N:
        try_lis.append(A[::1])
        return   
    for v in range(1,M+1):
        if v>=A[-1]:
            A.append(v)
            dfs(A)
            A.pop()
dfs([1])
total=0
for one_case in try_lis:
    tmp=0
    for j in S:
        if one_case[j[1]-1]-one_case[j[0]-1]==j[2]:
            tmp+=j[3]

    total=max(total,tmp)

print(total)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(1000000) 
ans = 0
def main():
    N, M, Q = map(int, readline().split())
    query = []
    for _ in range(Q):
        a, b, c, d = map(int, readline().split())
        a -= 1
        b -= 1
        query.append((a, b, c, d))

    def slv(A):    
        s = 0
        for a, b, c, d in query:
            if A[b]-A[a] == c:
                s += d
        return s
    
    
    from collections import deque 
    A = deque()
    def dfs(p):
        global ans
        if p == N:
            s = 0
            for a, b, c, d in query:
                if A[b]-A[a] == c:
                    s += d
            ans = max(s, ans)
            return
        if len(A) == 0:
            k = 1
        else:
            k = A[p-1]
        for i in range(k, M+1):
            A.append(i)
            dfs(p+1)
            A.pop()
    dfs(0)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(1000000) 
ans = 0
def main():
    N, M, Q = map(int, readline().split())
    query = []
    for _ in range(Q):
        a, b, c, d = map(int, readline().split())
        a -= 1
        b -= 1
        query.append((a, b, c, d))

    def slv(A):    
        s = 0
        for a, b, c, d in query:
            if A[b]-A[a] == c:
                s += d
        return s
    
    
    from collections import deque 
    A = deque()
    def dfs(p):
        global ans
        if p == N:
            s = 0
            for a, b, c, d in query:
                if A[b]-A[a] == c:
                    s += d
            ans = max(s, ans)
            return
        if len(A) == 0:
            k = 1
        else:
            k = A[p-1]
        for i in range(k, M+1):
            A.append(i)
            dfs(p+1)
            A.pop()
    dfs(0)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
N, M, Q = map(int, input().split())
abcd_list = [list(map(int, input().split())) for _ in range(Q)]
Alist = []
def dfs(array):
    if len(array) == N:
        Alist.append(array)
    else:
        if not array:
            for i in range(1, M+1):
                dfs(array[:] + [i])
        else:
            for i in range(array[-1], M+1):
                dfs(array[:] + [i])
dfs([])
ans = 0
for A in Alist:
    res = 0
    for a, b, c, d in abcd_list:
        if A[b-1] - A[a-1] == c:
            res += d
    ans = max(ans, res)
print(ans)

Solution (Python):
N, M, Q = map(int, input().split())
abcd_list = [list(map(int, input().split())) for _ in range(Q)]
Alist = []
def dfs(array):
    if len(array) == N:
        Alist.append(array)
    else:
        if not array:
            for i in range(1, M+1):
                dfs(array[:] + [i])
        else:
            for i in range(array[-1], M+1):
                dfs(array[:] + [i])
dfs([])
ans = 0
for A in Alist:
    res = 0
    for a, b, c, d in abcd_list:
        if A[b-1] - A[a-1] == c:
            res += d
    ans = max(ans, res)
print(ans)

Solution (Python):
N, M, Q = map(int, input().split())
abcd_list = [list(map(int, input().split())) for _ in range(Q)]
Alist = []
def dfs(array):
    if len(array) == N:
        Alist.append(array)
    else:
        if not array:
            for i in range(1, M+1):
                dfs(array[:] + [i])
        else:
            for i in range(array[-1], M+1):
                dfs(array[:] + [i])
dfs([])
ans = 0
for A in Alist:
    res = 0
    for a, b, c, d in abcd_list:
        if A[b-1] - A[a-1] == c:
            res += d
    ans = max(ans, res)
print(ans)

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

from itertools import combinations_with_replacement

ans=0
for a in combinations_with_replacement(range(1, m+1,), n):
    d=0
    for i in range(q):
        if a[abcd[i][1]-1]-a[abcd[i][0]-1]==abcd[i][2]:
            d+=abcd[i][3]
    ans=max(ans,d)
print(ans)

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


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


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


print(dfs([]))

Solution (Python):
from itertools import combinations_with_replacement as c

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

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

for i in c(range(1,m+1),n):
    s=0
    for j in Q:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            s+=j[3]
    a=max(a,s)
print(a)

Solution (Python):
def dfs(seq):
    
    ans = 0
    if len(seq) == n:
        
        score_ret = 0
        for a, b, c, d in req:
            if seq[b-1] - seq[a-1] == c:
                score_ret += d
        return score_ret  
    else:
        
        for i in range(seq[-1], m + 1):
            seq_next = seq + (i,)  
            score = dfs(seq_next)  
            ans = max(ans, score)  
 
    
    return ans
 
 
n, m, q = list(map(int, input().split()))

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



ans = 0
score = dfs((1,))
ans = max(ans, score)
print(ans)

Solution (Python):
def calc(l):
  t=0
  for ai,bi,ci,di in zip(a,b,c,d):
    if l[bi]-l[ai]==ci:
      t+=di
  return t

def dfs(l):
  if len(l)==n:
    return calc(l)
  res=0
  prev_last=0
  if len(l)>0:
    prev_last=l[-1]
  for v in range(prev_last,m):
    l.append(v)
    res=max(res,dfs(l))
    l.pop()
  return res

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)

print(dfs([]))

Solution (Python):
from itertools import combinations_with_replacement

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

result = 0

for x in combinations_with_replacement(range(1, m+1), n):
    t = 0
    for a,b,c,d in abcd:
        if x[b-1] - x[a-1] == c:
            t += d
    result = max(result,t)
print(result)

Solution (Python):
nmq=list(map(int, input().split()))
N=nmq[0]
M=nmq[1]
Q=nmq[2]
ablist=[]
for i in range(Q):
    tp=tuple(map(int, input().split()))
    ablist.append(tp)
sumlist=[]
alist=[i for i in range(1,M+1)]
import itertools
case=list(itertools.combinations_with_replacement(alist,N))
for nowcase in case:
    sumd=0
    for i in range(Q):
        if nowcase[ablist[i][1]-1]-nowcase[ablist[i][0]-1]==ablist[i][2]:
            sumd+=ablist[i][3]
    sumlist.append(sumd)
print(max(sumlist))

Solution (Python):
def dfs(seq):
    
    ans = 0
    if len(seq) == n:
        
        score_ret = 0
        for a, b, c, d in req:
            if seq[b-1] - seq[a-1] == c:
                score_ret += d
        return score_ret  
    else:
        
        for i in range(seq[-1], m + 1):
            seq_next = seq + (i,)  
            score = dfs(seq_next)  
            ans = max(ans, score)  

    
    return ans


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

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




ans = 0
score = dfs((1,))
ans = max(ans, score)
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 = list(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):
from sys import stdin, setrecursionlimit


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

    arr = []

    def dfs(num, ai):
        if len(ai) == n:
            arr.append(ai)
        elif len(ai) < n:
            for i in range(num, m + 1):
                dfs(i, ai + [i])

    ans = 0

    dfs(1, [])

    for ai in arr:
        score = 0
        for a, b, c, d in abcd:
            if ai[b - 1] - ai[a - 1] == c:
                score += d
        if ans < score:
            ans = score

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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

dic = {}
for i in range(Q):
  a, b, c, d = map(int, input().split())
  dic[(a-1, b-1, c-1)] = d
ans = 0
for ar in itertools.combinations_with_replacement(range(1, M+1), N):
  D = 0
  for com in dic.keys():
    if ar[com[1]] - ar[com[0]] == com[2]+1:
      D += dic[com]
  if D > ans:
    ans = D
print(ans)

Solution (Python):
from itertools import combinations_with_replacement as c
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for _ in range(q)]
a=0
for i in c(range(1,m+1),n):
    s=0
    for j in Q:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            s+=j[3]
    a=max(a,s)
print(a)

Solution (Python):
from itertools import combinations_with_replacement

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

ans = 0

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

print(ans)

Solution (Python):
import heapq

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

res = []
def dfs(current, n, m):
    if len(current) == n:
        res.append(current)
        return
    last = current[-1]
    for i in range(last, m+1):
        nex = current[::1]
        nex.append(i)
        dfs(nex, n, m)
for i in range(1, m+1):
    dfs([i], n, m)

max_p = 0
for r in res:
    p = 0
    for query in abcds_list:
        a, b, c, d = query
        if r[b-1] - r[a-1] == c:
            p += d
    if p > max_p:
        max_p = p
print(max_p)

Solution (Python):

def calc(nums):
    ret = 0
    for a, b, c, d in req:
        if nums[b - 1] - nums[a - 1] == c:
            ret += d
 
    return ret
 
 
n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]
 
ans = 0
 
stack = []
 

for i in range(1, m + 1):
    stack.append([i])
 
while stack:
    seq = stack.pop()
 
    if len(seq) == n:
        score = calc(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            stack.append(seq_next)
 
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()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
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()
lista = []
for i in range(Q):
    a, b, c, d = getNM()
    lista.append([a - 1, b - 1, c, d])

ans = 0
def dfs(i, numlist):
    if i == N:
        
        cnt = 0
        for jud in lista:
            if numlist[jud[1]] - numlist[jud[0]] == jud[2]:
                cnt += jud[3]
        return cnt

    ans = 0
    
    sta = 0
    
    if i > 0:
        sta = numlist[i - 1]
    
    
    for j in range(sta, M):
        
        numlist[i] = j
        ans = max(ans, dfs(i + 1, numlist))
    return ans
print(dfs(0, [0] * N))

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())
    a[i] -= 1
    b[i] -= 1
    
def score(A):
    tmp = 0
    for ai,bi,ci,di in zip(a,b,c,d):
        if A[bi]-A[ai]==ci:
            tmp += di
    return tmp
    
def dfs(A):
    if len(A)==N:
        return score(A)
    res = 0
    prev_last = A[-1] if len(A)>0 else 0
    for v in range(prev_last,M):
        A.append(v)
        res = max(res,dfs(A))
        A.pop()
    return res
print(dfs([]))

Solution (Python):
import itertools

if __name__ == '__main__':
    nmq = input()
    nmq = nmq.split()
    n = int(nmq[0])
    m = int(nmq[1])
    q = int(nmq[2])

    abcd = [0]*q
    for i in range(q):
        ele = input()
        ele = ele.split()
        ele = list(map(int,ele))
        abcd[i] = ele

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

    comb_list = list(itertools.combinations_with_replacement(comb,n))


    max_amount = 0
    for i in range(len(comb_list)):
        amount = 0
        for j in range(q):
            if (comb_list[i][abcd[j][1]-1] - comb_list[i][abcd[j][0]-1]) == abcd[j][2]:
                amount += abcd[j][3]
        max_amount = max(max_amount,amount)

    print(max_amount)

Solution (Python):

import sys
import itertools
import numpy as np
 
read = sys.stdin.buffer.read 
readline = sys.stdin.buffer.readline 
readlines = sys.stdin.buffer.readlines 

N, M, Q = map(int, readline().split())
 
A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))







n = len(A)
score = np.zeros(n, np.int32)
m = map(int, read().split())
for a, b, c, d in zip(m, m, m, m):
    cond = A[:, b - 1] - A[:, a - 1] == c 
    score += d * cond
 
print(score.max())

Solution (Python):
import sys

def ket(anw,m):
    wk=len(anw)
    while sum(anw)<=wk*m:
        anw[wk-1]+=1
        for i in range(wk-1,-1,-1):
            if anw[i]<m+1:
                return(anw)
            else:
                anw[i-1]+=1
                for j in range(i,wk):
                    anw[j]=anw[i-1]
    anw=[0]*wk
    return(anw)

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

wk = 0
an = [1]*n
anw = [1]*n
ten = tenw = 0
while sum(anw)<=n*m:
    for k in range(q):
        if anw[abcd[k][1]-1]-anw[abcd[k][0]-1]==abcd[k][2]:
            tenw += abcd[k][3]
        else:
            pass
    if ten < tenw:
        ten = tenw
        an = anw.copy()
        tenw = 0
    else:
        tenw = 0

    anw = ket(anw,m)
    if sum(anw) == 0:
        break

if ten == 0:
    print(0)
else:
    print(ten)

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

N, M, Q = map(int, input().split())
a = []
b = []
c = []
d = []
for i in range(Q):
    abcd = list(map(int, input().split()))
    a.append(abcd[0])
    b.append(abcd[1])
    c.append(abcd[2])
    d.append(abcd[3])
A_max = 0
A = [1] * N
def DFS():
    global A_max
    d_sum = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            d_sum += d[i]
    A_max = max(A_max, d_sum)
    if A[0] == M:
        return
    elif A[N-1] != M:
        A[N-1] += 1
    else:
        tmp_index = N-1
        while True:
            tmp_index -= 1
            if A[tmp_index] != M:
                A[tmp_index:] = [A[tmp_index] + 1] * len(A[tmp_index:])
                break
    DFS()

DFS()
print(A_max)

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

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

Solution (Python):
def solve(string):
    from itertools import combinations_with_replacement
    n, m, q, *abcd = map(int, string.split())
    ans = 0
    for v in combinations_with_replacement(range(1, m + 1), n):
        ans = max(
            ans,
            sum(d if v[b - 1] - v[a - 1] == c else 0 for a, b, c, d in zip(*[iter(abcd)] * 4)))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
def solve(string):
    from itertools import combinations_with_replacement
    n, m, q, *abcd = map(int, string.split())
    ans = 0
    for v in combinations_with_replacement(range(1, m + 1), n):
        v = sorted(list(v))
        ans = max(
            ans,
            sum(d if v[b - 1] - v[a - 1] == c else 0 for a, b, c, d in zip(*[iter(abcd)] * 4)))
    return str(ans)


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Solution (Python):
from itertools import combinations_with_replacement

n, m, q = map(int, (input().split()))
lst = [list(map(int, input().split())) for i in range(q)]
ptn = combinations_with_replacement(range(1, m + 1), n)
ans = 0

for p in ptn:
    s = 0
    for l in lst:
        if p[l[1] - 1] - p[l[0] - 1] == l[2]:
            s += l[3]
    ans = max(ans, s)

print(ans)

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

data = []
for n in range(Q):
    data.append([ int(i) for i in input().strip().split(' ')])

x = [ 1+i for i in range(M)]
max_total = 0
for A in itertools.combinations_with_replacement(x, N):
    total = 0
    for a,b,c,d in data:
        if A[b-1] - A[a-1] == c:
            total += d
    
    if max_total < total:
        max_total = total
print(max_total)

Solution (Python):
import itertools

def abcd(n):
  for _ in range(n):
    a,b,c,d = map(int,input().split())
    yield a,b,c,d

def main():
  N,M,Q = map(int,input().split())
  num = list(range(1,M+1))
  X = list(abcd(Q))
  for v in itertools.combinations_with_replacement(num, N):
    ans = 0
    for a,b,c,d in X:
      A,B = v[a-1],v[b-1]
      if B-A == c:
        ans += d
    yield ans

print(max(main()))

Solution (Python):
import itertools
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for _ in range(q):
    li=list(map(int,input().split()))
    a.append(li[0])
    b.append(li[1])
    c.append(li[2])
    d.append(li[3])



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



max_score=0
for j in range(len(h)):
    score=0
    for i in range(q):
        if h[j][b[i]-1]-h[j][a[i]-1]==c[i]:
            score+=d[i]
    max_score=max(max_score,score)

print(max_score)

Solution (Python):
import itertools

N, M, Q = map(int, input().split())
Arr = [list((map(int, input().split()))) for i in range(Q)]
Alist = list(itertools.combinations_with_replacement(range(1, M+1), N))
result = 0

for A in Alist:
    score = 0
    for q in range(Q):
        if A[Arr[q][1]-1] - A[Arr[q][0]-1] == Arr[q][2]:
            score += Arr[q][3]
    result = max(result, score)

print(result)

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


a_l = [0]*Q
b_l = [0]*Q
c_l = [0]*Q
d_l = [0]*Q
for i in range(Q):
    a_l[i], b_l[i], c_l[i], d_l[i] = map(int, input().split())

def calc_score(now):
    score = 0
    for a, b, c, d in zip(a_l, b_l, c_l, d_l):
        a -= 1
        b -= 1
        if c == (now[b]-now[a]):
            score += d

    return score

def dfs(now, n, num): 
    if n == 0:
        score_list.append(calc_score(now))
    else:
        for i in range(num, M+1):
            dfs(now+[i], n-1, i)

score_list = []
dfs([], N, 1)
print(max(score_list))

Solution (Python):
from itertools import combinations_with_replacement


def main():
    n, m, q = map(int, input().split())
    abcd = []
    for i in range(q):
        tmp = list(map(int, input().split()))
        tmp[0] -= 1
        tmp[1] -= 1
        abcd.append(tmp)
    

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

    return


if __name__ == "__main__":
    main()

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


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

def dfs(now, n, num): 
    if n == 0:
        make_group.append(now)
    else:
        for i in range(num, M+1):
            dfs(now+[i], n-1, i)

make_group = []
dfs([], N, 1)
ans = 0
for group in make_group:
    tmp = 0
    for q in Q_li:
        a = q[0] - 1
        b = q[1] - 1
        if q[2] == (group[b] - group[a]):
            tmp += q[3]
    ans = max(ans, tmp)
print(ans)