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

Solution (Python):
N,M,Q = map(int,input().split())
ABCD = [list(map(int,input().split())) for _ in range (Q)]
import sys
sys.setrecursionlimit(10**9)
Alist = []
def dfs(v):
    if len(v)==N:
        Alist.append(v)
        return 
    for t in range(v[-1],M+1):
        dfs(v+[t])
dfs([1])

ans = 0
for A in Alist:
    res = 0
    for a,b,c,d in ABCD:
        if A[b-1]-A[a-1]==c:
            res += d
    ans = max(ans,res)
print(ans)

Solution (Python):
import itertools
n,m,q=map(int, input().split())
S = []
for i in range(q):
    a,b,c,d=map(int, input().split())
    S.append([a,b,c,d])
tl=itertools.combinations_with_replacement(range(1,m+1),n)
ans = 0
for l in tl:
    t = 0
    for a,b,c,d in S:
        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())
P=[]
for inp in range(q):
    a,b,c,d=map(int,input().split())
    P.append((a,b,c,d))

now=[]
stc=[now[:]]
res=[]

def saiki(x,c,ma,n):
    if c== n:
        
        res.append(now[:])
        return
    
    for i in range(x,ma+1):
        now.append(i)
        saiki(i,c+1,ma,n)
        now.pop()

saiki(1,0,m,n)  

max_score=0
for C in res:
    score=0
    for i in range(q):
        if C[P[i][1]-1]-C[P[i][0]-1]==P[i][2]:
            score+=P[i][3]
    max_score=max(score,max_score)

print(max_score)

Solution (Python):
import sys
import itertools

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline


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


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


def dfs(i, mx):
    if i == N:
        return calc()

    score = 0
    for x in range(mx, M+1):
        A[i] = x
        s = dfs(i+1, x)
        score = max(s, score)
    return score


A = [0] * N
ans = dfs(0, 1)
print(ans)

Solution (Python):
from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [list(map(int, input().split())) for _ in range(Q)]

ans = []
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans.append(z)
    z = 0
print(max(ans))

Solution (Python):
from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans = max(ans, z)
    z = 0
print(ans)

Solution (Python):


import math

input_1 = input()
n = int(input_1.split(" ")[0])
m = int(input_1.split(" ")[1])
q = int(input_1.split(" ")[2])

input_array = []
for i in range(q):
    input_array.append(input())

array = []
for i in range(q):
    array.append(input_array[i].split(" "))

for i in range(q):
    for j in range(4):
        array[i][j] = int(array[i][j])







def make_all_combi(m, n, array):
    if n == 0:
        for i in range(m-1):
            array = array + [0]
        return array
    elif m == 1:
        for i in range(n):
            array = array + [1]
        return array
    else:
        array_3 = array + [1]
        array_4 = array + [0]
        tmp_list_a = make_all_combi(m, n-1, array_3)
        tmp_list_b = make_all_combi(m-1, n, array_4)
    return tmp_list_a + tmp_list_b

combi = make_all_combi(m, n, [])


def make_a(combi):
    A = []
    for i in range(len(combi)//(m+n-1)):
        list_a = combi[i*(m+n-1):(i+1)*(m+n-1)]
        count = 1
        a_cand = []
        for j in range(len(list_a)):
            if list_a[j] == 0:
                count = count + 1
            else:
                a_cand.append(count)
        A.append(a_cand)
    return A

A = make_a(combi)

score = 0
max_a = []
for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if A[i][array[j][1]-1] - A[i][array[j][0]-1] == array[j][2]:
            tmp = tmp + array[j][3]
    if tmp > score:
        score = tmp
        max_a = A

print(score)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
ans = 0
def main():
    N, M, Q = map(int, readline().split())
    query = []
    for _ in range(Q):
        a, b, c, d = map(int, readline().split())
        query.append((a, b, c, d))
    

    def getScore(A):
        res = 0
        for a, b, c, d in query:
            if A[b-1]-A[a-1] == c:
                res += d
        return res

    A = deque()
    def dfs():
        global ans
        n = len(A)
        if n == N:
            ans = max(getScore(A), ans)
        else:
            if n == 0:
                k = 1
            else:
                k = A[-1]
            for i in range(k, M+1):
                A.append(i)
                dfs()
                A.pop()
    dfs()
    print(ans)          
if __name__ == '__main__':
    main()

Solution (Python):
N,M,Q=map(int,input().split())
terms=[list(map(int,input().split())) for i in range(Q)]
def dfs(nums,length,min_lim):
    ans=0
    if length==N:
        ans_2=0
        for a,b,c,d in terms:
            if nums[b-1]-nums[a-1]==c:
                ans_2+=d
        return ans_2
    else:
        for i in range(min_lim,M+1):
            new_nums=nums+[i]
            ans_2=dfs(new_nums,length+1,i)
            ans=max(ans,ans_2)
    return ans
print(dfs([],0,1))

Solution (Python):
import itertools
import numpy as np

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

a = range(1,M+1)
arr = np.asarray(list(itertools.combinations_with_replacement(a,N))) 


sc = np.zeros(arr.shape[0],dtype=int)


for i in range(Q):
  abcd = list(map(int, input().split()))
  f = (arr[:,abcd[1]-1]-arr[:,abcd[0]-1])==abcd[2]
  sc += abcd[3]*f 

print(sc.max())

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 itertools
N,M,Q=map(int,input().split())
a_b_c_d=[list(map(int,input().split())) for _ in range(Q)]
nums=[i for i in range(1,M+1)]
A_s=itertools.combinations_with_replacement(nums,N)
ans=0
for A in A_s:
    tmp=0
    for i in range(Q):
        if A[a_b_c_d[i][1]-1]-A[a_b_c_d[i][0]-1]==a_b_c_d[i][2]:
            tmp+=a_b_c_d[i][3]
    if tmp>ans:
        ans=tmp
print(ans)

Solution (Python):
from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [list(map(int, input().split())) for _ in range(Q)]

ans = []
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans.append(z)
    z = 0
print(max(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(1, m+1), 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 itertools
N, M, Q = map(int, input().split())

suretu = list(itertools.combinations_with_replacement(list(range(1,M+1)),N))
arr = [list(map(int, input().split())) for _ in range(Q)]

max_point = 0
for item in suretu:
    point =0
    for jtem in arr:
        if item[jtem[1]-1] - item[jtem[0]-1] == jtem[2]:
            point += jtem[3]

    if point > max_point:
        max_point = point

print(max_point)

Solution (Python):
N ,M ,Q = map(int,input().split())
l = [list(map(int,input().split())) for i in range(Q)]
ans=[]
score = 0
for i1 in range(1,M+1):
    for i2 in range(i1,M+1):
        for i3 in range(i2,M+1):
            for i4 in range(i3,M+1):
                for i5 in range(i4,M+1):
                    for i6 in range(i5,M+1):
                        for i7 in range(i6,M+1):
                            for i8 in range(i7,M+1):
                                for i9 in range(i8,M+1):
                                    for i10 in range(i9,M+1):
                                        A = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        for a, b, c, d in l:
                                            if A[b-1] - A[a-1] == c:
                                                score += d
                                            else:
                                                pass
                                        ans.append(score)
                                        score = 0
print(max(ans))

Solution (Python):
import itertools
n,m,q=map(int,input().split())
X=[]
B=[]
for i in range(q):
    X.append(list(map(int,input().split())))
for A in itertools.combinations_with_replacement(range(1,m+1),n):
    ans=0
    for x in X:
        if A[x[1]-1]-A[x[0]-1]==x[2]:
            ans+=x[3]
    B.append(ans)
print(max(B))

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

Solution (Python):
import sys
import itertools

def main():
    N, M, Q = map(int, input().split())
    ABCD = [[int(_) for _ in input().split()] for i in range(Q)]
    value_range = list(range(1, M+1))
    seq_list = list(itertools.combinations_with_replacement(value_range, N))

    max_score = 0
    for i_seq in seq_list:
        score = 0
        for a, b, c, d in ABCD:
            if (i_seq[b-1] - i_seq[a-1]) == c:
                score += d

        max_score = max(max_score, score)

    print(max_score)
    return

if __name__ == '__main__':
    main()
    sys.exit(0)

Solution (Python):
from itertools import combinations_with_replacement


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

max_total = 0

A_ls = list(combinations_with_replacement(range(1, M+1), N))

for A in A_ls:
    total = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            total += d[i]
    max_total = max(max_total, total)

print(max_total)

Solution (Python):
import itertools  

N,M,Q=map(int,input().split())
As = list(itertools.combinations_with_replacement(range(1,M+1),N))

nums=[[0,0,0,0]for i in range(Q)]
ans =[]
for i in range(Q):
    nums[i] = list(map(int, input().split()))

for A in As:
    t=0
    for i in range(Q):
        if A[nums[i][1]-1]-A[nums[i][0]-1] == nums[i][2]:
            t += nums[i][3]  

    ans.append(t)

print(max(ans))

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


import copy

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

for i in range(1, m + 1):
	seq_arr.append([i])

for i in range(n):
	tmp_arr = []
	
	for s in seq_arr:
		for j in range(s[-1], m + 1):
			tmp_arr.append(s + [j])

	seq_arr = copy.deepcopy(tmp_arr)

queries = []

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

ans = 0

for seq in seq_arr:
	sum = 0
	
	for query in queries:
		a, b, c, d = query
		
		if seq[b] - seq[a] == c:
			sum += d
			
	ans = max(ans, sum)

print(ans)

Solution (Python):
def setse(s, m, i):
    if i < 0:
        return
    s[i] += 1
    if s[i] > m:
        setse(s, m, i - 1)
        if i > 0:
            s[i] = s[i - 1]

n, m, q = map(int, input().split(' '))
a = []
j = [1] * n
sc, scm = 0, 0
for i in range(q):
    al = list(map(int, input().split(' ')))
    a.append(al)
while(j[0] <= m):
    for i in a:
        sc += i[3] if j[i[1] - 1] - j[i[0] - 1] == i[2] else 0
    setse(j, m, n - 1)
    scm = sc if scm < sc else scm
    sc = 0
print(scm)

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

A = [0] * N
A[0] = 1
result = []


def dfs(d, n, A):
    
    if d > N or n > M:
        return
    
    A[d - 1] = n

    
    if d == N:
        total = 0
        for i in range(Q):
            ai = abcd[i][0]
            bi = abcd[i][1]
            ci = abcd[i][2]
            di = abcd[i][3]
            if A[bi - 1] - A[ai - 1] == ci:
                total += di
        result.append(total)

    dfs(d + 1, n, A)
    dfs(d, n + 1, A)


dfs(2, 1, A)

print(max(result))

Solution (Python):
from itertools import combinations_with_replacement

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

ans = 0
_N = N
if N < M:
    _N = M

for A in combinations_with_replacement(range(1, M + 1), _N):
    tmp = 0
    for a, b, c, d in L:
        if a <= _N and b <= _N and A[b - 1] - A[a - 1] == c:
            tmp += d

    if tmp > ans:
        ans = tmp

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for _ in range(q)]
ans=0
def dfs(i,tab,ma):
	global ans
	if i==n:
		t=0
		for a,b,c,d in Q:
			if tab[b-1]-tab[a-1]==c:
				t+=d
		if t>ans:
			ans=t
		return
	for j in range(ma,m+1):
		dfs(i+1,tab+[j],j)
dfs(0,[],1)
print(ans)

Solution (Python):
import itertools

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

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

print(ans)

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

def score(A):
    ans = 0
    for i in abcd:
        if A[i[1] -1] - A[i[0] -1] == i[2]:
            ans += i[3]
    return ans

def dfs(A, i):
    ans = 0
    if i == N:
        return score(A)
    
    lower = 1
    if i != 0:
        lower = A[i-1]
    for x in range(lower, M+1):
        A[i] = x
        ans = max(ans, dfs(A, i+1))
    
    return ans

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

Solution (Python):
from collections import deque

N,M,Q = map(int,input().split())
QUERY = [0]*Q
for i in range(Q):
    QUERY[i] = tuple(map(int,input().split()))

ans = 0
D = deque()
D.append(-1)
D.append(1)
dlen = 2
A = deque()
Alen = 0
while dlen != 0:
    f = D.pop()
    dlen -= 1
    if f == -1:
        A.pop()
        Alen -= 1
        continue
    A.append(f)
    Alen += 1
    if Alen == N:
        e = 0
        for a,b,c,d in QUERY:
            a -= 1
            b -= 1
            if A[b] - A[a] == c:
                e += d
        ans = max(ans,e)
    else:
        for AA in range(A[-1],M+1):
            D.append(-1)
            D.append(AA)
            dlen += 2

print(ans)

Solution (Python):
N, M, Q =  map(int, input().split())
List = [list(map(int, input().split())) for _ in range(Q)]
A = [1 for _ in range(N)]
ans = 0

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

def new_A(A):
  for i in range(N):
    if A[N-i-1] < M:
      A[N-i-1] += 1
      break
    elif A[N-i-1] == M and A[N-i-2] < M:
      A[N-i-2] += 1
      for x in range(N-i-1, N):
        A[x] = A[N-i-2]
      break
  return A

for j in range(cmb(N+M-1, N)):
  sum = 0
  for k in range(Q):
    if A[List[k][1]-1] - A[List[k][0]-1] == List[k][2]:
      sum += List[k][3]
  if ans < sum:
    ans = sum
  A = new_A(A)
print(ans)

Solution (Python):
edges=[]
N,M,Q=map(int,input().split())
conditions=[]
for i in range(Q):
    a,b,c,d=map(int,input().split())
    conditions.append([a,b,c,d])
for i in range(M):
    edges.append(list(range(i+1,M+1)))
A=[]
score=0
score_list=[]
def dfs(x,N,M):
    A.append(x)
    score=0
    if len(A)<N:
        for i in edges[x-1]:
            dfs(i,N,M)
            if i==edges[x-1][-1]:
                A.pop()
    elif len(A)==N:
        for i in range(Q):
            if A[conditions[i][1]-1]-A[conditions[i][0]-1]==conditions[i][2]:
                score+=conditions[i][3]
            if i==Q-1:
                score_list.append(score)                
        A.pop()
dfs(1,N,M)


print(max(score_list))

Solution (Python):
import itertools
n,m,q = map(int,input().split())
inputList = []
for i in range(1,q+1):
    abcd = list(map(int,input().split()))
    inputList.append(abcd)
AList =  list(itertools.combinations_with_replacement(range(1,m+1), n))
PointList = []
for array in AList:
    point = 0
    for iList in inputList:
        if array[iList[1]-1] - array[iList[0]-1] == iList[2]:
            point = point + iList[3]
    PointList.append(point)
print(max(PointList))

Solution (Python):
import copy

arrays = []
n,m,q = 0,0,0

def main():
    global n, m, q
    global arrays
    n, m, q = map(int, input().split())
    abcd = [list(map(int, input().split())) for _ in range(q)]
    ans = 0
    dfs([], 1)
    for array in arrays:
        tmp = 0
        for i in range(q):
            if array[abcd[i][1]-1] - array[abcd[i][0]-1] == abcd[i][2]:
                tmp += abcd[i][3]
        ans = max(ans, tmp)
    print(ans)

def dfs(stack, i):
    stack.append(i)
    if len(stack) == n:
        arrays.append(copy.deepcopy(stack))
        if i < m:
            stack.pop()
            dfs(copy.deepcopy(stack), i + 1)
        return
    dfs(copy.deepcopy(stack), i)
    if i < m:
        stack.pop()
        dfs(copy.deepcopy(stack), i + 1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,M,Q=map(int, input().split())
    ABCD=[tuple(map(int, input().split())) for _ in range(Q)]

    def f(l):
        res=0
        for a,b,c,d in ABCD:
            if l[b]-l[a]==c: res+=d
        return res

    ans=0
    stk=[[1]]
    while stk:
        l=stk.pop()
        if len(l)==N+1:
            ans = max(ans, f(l))
        else:
            for i in range(l[-1],M+1):
                stk.append(l+[i])
    print(ans)

if __name__ == '__main__':
    main()