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())
l=[list(map(int,input().split())) for i in range(q)]
L=[]
for i in range(1,m+1):
  if n==1:
    L.append((i))
  else:
    for i2 in range(i,m+1):
      if n==2:
        L.append((i,i2))
      else:
        for i3 in range(i2,m+1):
          if n==3:
            L.append((i,i2,i3))
          else:
            for i4 in range(i3,m+1):
              if n==4:
                L.append((i,i2,i3,i4))
              else:
                for i5 in range(i4,m+1):
                  if n==5:
                    L.append((i,i2,i3,i4,i5))
                  else:
                    for i6 in range(i5,m+1):
                      if n==6:
                        L.append((i,i2,i3,i4,i5,i6))
                      else:
                        for i7 in range(i6,m+1):
                          if n==7:
                            L.append((i,i2,i3,i4,i5,i6,i7))
                          else:
                            for i8 in range(i7,m+1):
                              if n==8:
                                L.append((i,i2,i3,i4,i5,i6,i7,i8))
                              else:
                                for i9 in range(i8,m+1):
                                  if n==9:
                                    L.append((i,i2,i3,i4,i5,i6,i7,i8,i9))
                                  else:
                                    for i10 in range(i9,m+1):
                                      L.append((i,i2,i3,i4,i5,i6,i7,i8,i9,i10))
ans=[]
for i in range(len(L)):
  ct=0
  for j in range(q):
    if L[i][l[j][1]-1]-L[i][l[j][0]-1]==l[j][2]:
      ct+=l[j][3]
  ans.append(ct)
print(max(ans))

Solution (Python):
def main():
    N, M, Q = map(int, input().split())
    items = []

    for i in range(Q):
        items.append(tuple(map(int, input().split())))

    

    def list_a(a: list):
        if len(a) == N:
            return [a]
        else:
            arr = []
            if len(a) == 0:
                last = 1
            else:
                last = a[-1]

            for i in range(last, M + 1):
                arr += list_a(a + [i])
            return arr

    candidates = list_a([])
    

    max_score = -100
    max_A = None

    for A in candidates:
        score = 0
        for a, b, c, d in items:
            if A[b-1] - A[a-1] == c:
                score += d

        if score > max_score:
            max_score = score
            max_A = A

    print(max_score)


if __name__ == '__main__':
    main()

Solution (Python):
n,m,q=map(int,input().split())
e=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    e.append([a,b,c,d])
def calc(a):
    
    an=0
    for i in range(q):
        if a[e[i][1]-1]-a[e[i][0]-1]==e[i][2]:
            an+=e[i][3]
    return an
ans=[]
def ca(a,i,n,prev):
    if i==n:
        ans.append(calc(a))
    else:
        for j in range(prev,m+1):
            a[i]=j
            ca(a,i+1,n,j)

a=[0]*n 
ca(a,0,n,1)
print(max(ans))

Solution (Python):


import itertools

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

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

ans = 0
for l in list(itertools.combinations_with_replacement(nums, N)):
    tmp = 0
    for t in TEST:
        if l[t[1]-1]-l[t[0]-1] ==t[2]:
            tmp += t[3]
        else:
            continue
    ans = max(ans, tmp)

print(ans)

Solution (Python):
n,m,q=map(int,input().split())
ans=-float("INF")
l=[list(map(int,input().split())) for i in range(q)]
from itertools import combinations_with_replacement as pe
for i in pe(range(m),r=n):
    p=0
    for x,y,di,po in l:
        if i[y-1]-i[x-1]==di:p+=po
    ans=max(p,ans)
print(ans)

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


def gen_a(m, n):
    if n == 1:
        return {(i,) for i in range(1, m + 1)}
    else:
        bef_a = gen_a(m, n - 1)
        ret = set()
        for bef in bef_a:
            for i in range(bef[-1], m + 1):
                ret.add(bef + (i,))
        return ret


ans = 0
for a_tuple in gen_a(m, n):
    score_a = 0
    for a, b, c, d in score:
        a, b = a - 1, b - 1
        if a_tuple[b] - a_tuple[a] == c:
            score_a += d
    ans = max(score_a, ans)

print(ans)

Solution (Python):
from itertools import combinations_with_replacement

N, M, Q = [int(x) for x in input().split()]
ABCD = [[int(x) for x in input().split()] for i in range(Q)]

best = 0
for combo in combinations_with_replacement(range(1, M + 1), r=N):
    score = 0
    for a, b, c, d in ABCD:
        assert 1 <= a < b <= N
        assert 0 <= c <= M - 1
        if combo[b - 1] - combo[a - 1] == c:
            score += d
    best = max(best, score)
print(best)

Solution (Python):
import itertools

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

Solution (Python):
import itertools
n,m,q = map(int,input().split())
num = [i for i in range(1,m+1)]
l = []
for i in range(q):
    r = list(map(int,input().split()))
    l.append(r)
l.sort()
stock = list(itertools.combinations_with_replacement(num, n))
ans = 0
for i in stock:
    s = 0
    for j in l:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            s += j[3]
            
        
    if ans < s:
        ans = s
print(ans)

Solution (Python):
from itertools import combinations_with_replacement

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

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

for _ in range(Q):
    x, y, z, w = map(int, input().split(' '))
    a.append(x)
    b.append(y)
    c.append(z)
    d.append(w)

max_score = 0

for A in combinations_with_replacement(range(1, M + 1), r=N):
    A = [None, *A]
    score = 0
    for i in range(1, Q + 1):
        if A[b[i]] - A[a[i]] == c[i]:
            score += d[i]
    max_score = max(score, max_score)

print(max_score)

Solution (Python):
from itertools import combinations
n, m, q = map(int, input().split())
abcd = []
for _ in range(q):
    a, b, c, d = map(int, input().split())
    abcd.append((a, b, c, d))

ans = 0
for i in combinations(list(range(1,n+m)), m-1):
    tmp = 1
    li = []
    for j in range(1, n+m):
        if j in i:
            tmp += 1
        else:
            li.append(tmp)
    score = 0
    for a, b, c, d in abcd:
        if li[b-1]-li[a-1]==c:
            score += d
    ans = max(ans, score)
print(ans)

Solution (Python):
def point(A, queries):
    ans = 0
    for query in queries:
        a, b, c, d = query
        if A[b - 1] - A[a - 1] == c:
            ans += d
    return ans

def next(A, M):
    for n in range(N):
        if A[N - n - 1] < M:
            A = A[:N - n - 1] + [A[N - n - 1] + 1] * (n + 1)
            return A
    return []



N, M, Q = map(int, input().split())
queries = [[int(i) for i in input().split()] for q in range(Q)]
A = [1] * N
ans = 0
while True:
    ans = max(ans, point(A, queries))
    A = next(A, M)
    if A == []:
        break
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
n,m,q = map(int,input().split())
x = [list(map(int,input().split()))for i in range(q)]
ans = 0
def calc(l):
    res = 0
    
    for i in range(q):
        a,b,c,d = x[i][0],x[i][1],x[i][2],x[i][3]
        a -= 1
        b -= 1
        if l[b] - l[a] == c:res += d
    return res
def dfs(d,nums):
    if d == n:
        
        return calc(nums)
    res = 0
    for i in range(1,m+1):
        if len(nums) > 0 and nums[-1] > i:continue
        res = max(res,dfs(d+1,nums + [i]))
    return res

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

Solution (Python):
import itertools

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

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

numbers = list(itertools.combinations_with_replacement(numbers, n))


ans = 0
tmp = 0

for i in range(len(numbers)):
    s = numbers[i]
    tmp = 0
    
    for j in range(q):
        if s[li[j][1]-1] - s[li[j][0]-1] == li[j][2]:
            tmp += li[j][3]
    ans = max(ans, tmp)

print(ans)

Solution (Python):
cin = open(0).read().strip().split('\n')
n, m, q = map(int, cin[0].split(' '))
abcd = [tuple(map(int, a.split(' '))) for a in cin[1:]]

ret = 0
import itertools
for case in itertools.combinations_with_replacement(list(range(1,m+1)), n):
    tmp = 0
    for c in abcd:
        if case[c[1]-1] - case[c[0]-1] == c[2]:
            tmp += c[3]
    ret = max(ret, tmp)
print(ret)

Solution (Python):
from collections import deque
import copy

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

abcd = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append((a,b,c,d))
    
q = deque([[1]])
for _ in range(N):
    ap = deque([])
    while q:
        p = q.pop()
        num = p[-1]
        for i in range(num,M+1):
            new_list = p+[i]
            ap.append(new_list)
    q = ap
    
ans = 0
for x in q:
    ret = 0
    for a,b,c,d in abcd:
        if x[b]-x[a] == c:
            ret += d
    ans = max(ans,ret)
    
print(ans)

Solution (Python):

import sys
import itertools

def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    result = 0
    for iter in itertools.combinations_with_replacement(range(1,M+1),N):
        l = sorted(list(iter))
        sum = 0
        for i in range(Q):
            if l[b[i]-1] - l[a[i]-1] == c[i]:
                sum += d[i]
        result = max(result,sum)
    print(result)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    Q = int(next(tokens))  
    a = [int()] * (Q)  
    b = [int()] * (Q)  
    c = [int()] * (Q)  
    d = [int()] * (Q)  
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()

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

_max = 0
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    score = sum([q[3] for q in Qs if A[q[1] - 1] - A[q[0] - 1] == q[2]])
    _max = score if _max < score else _max
print(_max)

Solution (Python):
from itertools import combinations


def solve(n, m, q, q_list):

    res_max = 0

    
    a_list = [0] * n
    for com in combinations(range(n + m - 1), n):

        for i, c in enumerate(com):
            if i == 0:
                a_list[i] = c + 1
            else:
                a_list[i] = a_list[i - 1] + c - com[i - 1] - 1
        
        res = 0
        for i in range(q):
            a, b, c, d = q_list[i]
            if a_list[b - 1] - a_list[a - 1] == c:
                res += d

        if res > res_max:
            res_max = res
    
    return res_max


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


def test():
    assert solve(3, 4, 3, [[1, 3, 3, 100], [1, 2, 2, 10], [2, 3, 2, 10]]) == 110
    assert solve(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]
    ]) == 357500
    assert solve(10, 10, 1, [[1, 10, 9, 1]]) == 1


if __name__ == "__main__":
    test()
    main()

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

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

import itertools

ans = {}

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

Solution (Python):
import sys
import math


def score(A, Q):
    q = len(Q)
    res = 0
    for i in range(q):
        if A[Q[i][1]] - A[Q[i][0]] == Q[i][2]:
            res += Q[i][3]
    return res


def calc(k, A, n, m, Q):
    if k == n:
        s = score(A, Q)
        return s

    start = 1
    if k >= 1:
        start = A[k - 1]

    res = 0
    for i in range(start, m + 1):
        A[k] = i
        res = max(res, calc(k + 1, A, n, m, Q))

    return res


def main():
    input = sys.stdin.readline

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

    A = [1 for i in range(n)]
    res = calc(0, A, n, m, Q)

    print(res)


main()

Solution (Python):
from itertools import combinations_with_replacement

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

query = tuple(tuple(map(int, input().split())) for _ in range(Q))

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

Solution (Python):
import itertools
N, M , Q = map(int,input().split())
suuji = [i for i in range(1,M+1)]
L = []
for i in range(Q):
  temp = list(map(int,input().split()))
  L.append(temp)



Aall = list(itertools.combinations_with_replacement(suuji, N))


ans = 0
for A in Aall:
  test = 0
  for i in range(Q): 
    
    
    if A[L[i][1]-1]-A[L[i][0]-1] == L[i][2]:
      test += L[i][3]
  ans = max(ans,test)
print(ans)

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))
  
comb = itertools.combinations_with_replacement(range(1,m+1), n)

max_score = 0
for e in comb:
  score = 0
  for j in l:
    if e[j[1]-1]-e[j[0]-1]==j[2]:
      
      score += j[3]
  if score > max_score:
    max_score = score
print(max_score)

Solution (Python):
import itertools
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])
one_to_m = [i+1 for i in range(m)]
A = list(map(list, list(itertools.combinations_with_replacement(one_to_m, n))))
maximum = 0
for line in A:
    score = 0
    for i in range(q):
        if c[i] == line[b[i]-1] - line[a[i]-1]:
            score += d[i]
    if maximum < score:
        maximum = score
print(maximum)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque

def main():
    N, M, Q = map(int, readline().rstrip().split())
    P = [tuple(map(int, readline().rstrip().split())) for _ in range(Q)]
    ans = 0
    l = [[i] for i in range(1, M+1)]
    que = deque(l)
    for i in range(N):
        for _ in range(len(que)):
            ll = que.popleft()
            for j in range(ll[-1], M+1):
                que.append(ll + [j])
    
    for pair in que:
        score = 0
        for a, b, c, d in P:
            if pair[b-1] - pair[a-1] == c:
                score += d
        ans = max(ans, score)
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
for i in range(q):
	x, y, z, w = map(int, input().split())
	x, y = x - 1, y - 1
	a.append(x)
	b.append(y)
	c.append(z)
	d.append(w)

import itertools
lst = list(range(1, m + 1)) 
A = list(itertools.combinations_with_replacement(lst, n))

maxs = 0
for v in A:
	score = 0
	for i in range(q):
		if v[b[i]] - v[a[i]] == c[i]:
			score += d[i]
	maxs = max(maxs, score)

print(maxs)

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

m = M - 1

def f(s):
    if len(s) == N:
        return [s]
    result = []
    if s == '':
        r = 0
    else:
        r = int(s[-1])
    for i in range(r, m + 1):
        result.extend(f(s + str(i)))
    return result

result = 0
V = f('')
for s in V:
    A = [int(c) + 1 for c in s]
    t = 0
    for a, b, c, d in abcd:
        if A[b - 1] - A[a - 1] == c:
            t += d
    result = max(result, t)
print(result)

Solution (Python):
import itertools


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

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

row = list(itertools.combinations_with_replacement(num, N))

point_max = 0
for i in range(len(row)):
    r = list(row[i])
    point = 0
    for j in range(Q):
        a = int_list[j][0]
        b = int_list[j][1]
        c = int_list[j][2]
        d = int_list[j][3]
        if r[b-1] - r[a-1] == c:
            point += d
    point_max = max(point, point_max)

print(point_max)

Solution (Python):
import copy
n, m, q = map(int, input().split())
candi = []

def calc(ar, s):
    if len(ar) == n:
        if s <= m: candi.append(ar)
        return
    max_num = ar[len(ar) - 1]
    for i in range(0, m-s+1):
        tmp = copy.deepcopy(ar)
        tmp.append(max_num+i)
        calc(tmp, s+i)

calc([1], 1)
tes = [list(map(int, input().split())) for _ in range(q)]
ans = 0

for now in candi:
    tmp = 0
    for cons in tes:
        a, b, c, d = cons[0], cons[1], cons[2], cons[3]
        if now[b-1] - now[a-1] == c: tmp += d
    ans = max(ans, tmp)
print(ans)

Solution (Python):
N, M, Q = [int(n) for n in 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] = [int(n) for n in input().split()]

def gen(i, n, m):
    if n == 0:
        yield []
        return
    for f in range(i, m + 1):
        for rest in gen(f, n - 1, m):
            yield [f] + rest

sm = 0
for A in gen(1,N,M):
    s = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            s += d[i]
    if s > sm:
        sm = s

print(sm)

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

A_list = [[1, i] for i in range(1, M+1)]
for i in range(2, N):
  t_list = []
  for e in A_list:
    for j in range(e[-1], M+1):
      t_list.append(e + [j])
  A_list = t_list



ans = 0
for A in A_list:
  t = 0
  for a, b, c, d in abcd:
    if (A[b-1] - A[a-1]) == c:
      t += d
  ans = max(ans, t)

print(ans)

Solution (Python):
import collections
def main():

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

    lv = [[1]]
    for i in range(N):
        temp = []
        for v in lv:
            for j in range(v[-1], M+1):
                temp.append(v + [j])
        lv = temp

    ans = 0
    for v in lv:
        q = 0
        for a, b, c in p:
            if v[b] - v[a] == c:
                q += p[(a, b, c)]
        ans = max(ans, q)
    return ans

if __name__ == '__main__':
    print(main())

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


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


for num in li:
    p = 0
    for point in points:
        if num[point[1] - 1] - num[point[0] - 1] == point[2]:
            p += point[3]
    ans = max(p, ans)


print(ans)

Solution (Python):
def resolve():
    import itertools
    n, m, q = map(int, input().split())
    cond = [list(map(int, input().split())) for _ in range(q)]
    pos = list(itertools.combinations_with_replacement(range(1, m+1), n))
    ans = 0
    for i in range(len(pos)):
        test = list(pos[i])
        point = 0
        for j in range(q):
            if test[cond[j][1]-1] - test[cond[j][0]-1] == cond[j][2]:
                point += cond[j][3]
        ans = max(ans, point)
    print(ans)
resolve()

Solution (Python):
n, m, q = map(int, input().split())
A, B, C, D = [], [], [], []
for i 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)

L = []

def f(l):
    if len(l) == n:
        L.append(l)
        return
    for i in range(l[-1], m + 1):
        f(l + [i])

for i in range(1, m + 1):
    f([i])

ans = 0

for l in L:
    ans = max(ans, sum(d for a, b, c, d in zip(A, B, C, D) if l[b] - l[a] == c))

print(ans)

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

for A in itertools.combinations_with_replacement(range(1, m + 1), n):
    flag = 0
    for k in range(n - 1):
        if A[k + 1] < A[k]:
            flag = 1
    if flag == 0:
        point = 0
        for l in range(q):
            if A[lst[l][1] - 1] - A[lst[l][0] - 1] == lst[l][2]:
                point += lst[l][3]
        ans = max(ans, point)

print(ans)

Solution (Python):
import sys
from itertools import combinations_with_replacement
def input(): return sys.stdin.readline().strip()


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

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



    


if __name__ == "__main__":
    main()

Solution (Python):

import sys


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    from itertools import combinations_with_replacement
    answer = 0
    for AA in combinations_with_replacement(range(1,M+1),r=N):
        
        tmp_ans = 0
        for q in range(Q):
            if AA[b[q]-1] - AA[a[q]-1] ==  c[q]:
                tmp_ans += d[q]
  
        answer = max(answer,tmp_ans)
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    Q = int(next(tokens))  
    a = [int()] * (Q)  
    b = [int()] * (Q)  
    c = [int()] * (Q)  
    d = [int()] * (Q)  
    for i in range(Q):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
        d[i] = int(next(tokens))
    solve(N, M, Q, a, b, c, d)

if __name__ == '__main__':
    main()

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

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

l = []

def perm(l1,i,depth):
    if depth == N:
        l.append(l1)
    else:
        for j in range(i,M+1):
            l2 = list(l1)
            l2.append(j)
            perm(l2,j,depth+1)

perm([],1,0)

ans = 0

def smax(a,b):
    if a>b:
        return a
    else:
        return b

for ll in l:
    score = 0
    for i in range(Q):
        if ll[D[i][1]-1]-ll[D[i][0]-1]==D[i][2]:
            score += D[i][3]
    ans =  smax(score,ans)


print(ans)

Solution (Python):
n,m,q = map(int,input().split())
xy = []
for _ in range(q):
  a,b,c,d = map(int,input().split())
  a = n-a
  b = n-b
  xy.append([a,b,c,d])
time = [0 for _ in range(n)]
def nex(time):
  cnt = 0
  for d in range(n):
    if time[d] == m-1:
      cnt += 1
    else:
      break
  if cnt == n:
    return 'over'
  else:
    se = time[cnt] + 1
  for d in range(cnt):
    time[d] = se
  time[cnt] += 1
  return time
can = []
while time != 'over':
  tmp = 0
  
  for x in xy:
    a,b,c,d = x
    
    if time[b] - time[a] == c:
      tmp += d
  can.append(tmp)  
  time = nex(time)
print(max(can))

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
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,B,C,D=map(int,input().split())
    a[i]=A;b[i]=B;c[i]=C;d[i]=D
r=[]
def dfs(i,depth,b,h):
    if depth==0:
        b.append(h)
        return
    for j in range(i,M+1):
        nh=h[:]
        nh.append(j)
        dfs(j,depth-1,b,nh)
dfs(1,10,r,[])
ans=0
for R in r:
    cnt=0
    for j in range(Q):
        if R[b[j]-1]-R[a[j]-1]==c[j]:
            cnt+=d[j]
    ans=max(cnt,ans)
print(ans)

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    
    

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

    def dfs(l):
        res = 0
        if len(l)==n:
            for a,b,c,d in abcd:
                if l[b-1]-l[a-1]==c:
                    res += d
            return res
        else:
            a = l[-1]
            for i in range(a, m+1):
                temp = l + [i]
                res = max(res, dfs(temp))
            return res
    print(dfs([1]))

if __name__ == '__main__':
    main()

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


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

max_score = 0

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

Solution (Python):
import itertools


N, M, Q = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]
ans = 0
for p in itertools.combinations_with_replacement(range(1, M+1), N):
    A = list(p)
    s = 0
    for a, b, c, d in query:
        s += d if A[b-1]-A[a-1] == c else 0
    ans = max(ans, s)
print(ans)

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

L = set()
def h(l):
    if len(l) == N:
        L.add(l)
        return
    s = 0
    if len(l) == 0:
        s = 1
    else:
        s = l[-1]
    for i in range(s, M+1):
        h(l + (i,))


h(())

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

ans = 0


for l in L:
    t = 0
    for a,b,c,d in z:
        if l[b] - l[a] == c:
            t += d
    ans = max(ans, t)

print(ans)

Solution (Python):

from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def possible_list(n, m):
    mlist = list(range(1, m+1))
    for comb in combinations_with_replacement(mlist, n):
        comb = sorted(comb)
        yield comb

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

    maxvalue = 0
    for l in possible_list(N, M):
        total = 0
        for a, b, c, d in constraints:
            if l[b-1] - l[a-1] == c:
                total += d
        if total > maxvalue:
            maxvalue = total

    print(maxvalue)


if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

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

print(ans)

Solution (Python):

import math
import itertools
import sys
import collections

def solve(N,M,Q,ABCD):
    ans = 0
    A = [i for i in range(1,M+1)]
    for p in itertools.combinations_with_replacement(A,N):
        tmp = 0
        for a,b,c,d in ABCD:
            if(p[b-1] - p [a-1] == c):
                tmp+=d
        ans = max(ans,tmp)
    return ans



def main():
    N ,M,Q = map(int,input().split())
    ABCD = []
    for _ in range(Q):
        ABCD.append(list(map(int,input().split())))
    
    print(solve(N,M,Q,ABCD))
if __name__ == '__main__':
   main()

Solution (Python):

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

Solution (Python):
n,m,q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(q):
	ai,bi,ci,di=map(int,input().split())
	a.append(ai)
	b.append(bi)
	c.append(ci)
	d.append(di)
from itertools import combinations_with_replacement as cmb
A=list(cmb(range(1,m+1),n))

ans=0
for lst in A:
	sum=0
	for i in range(q):
		if lst[b[i]-1]-lst[a[i]-1]==c[i]:
			sum+=d[i]
	ans=max(sum,ans)
print(ans)

Solution (Python):
from collections import *
ans = 0
def calc(l):
	global ans
	res = 0
	for i in q:
		if l[i[1]-1]-l[i[0]-1] == i[2]:
			res += i[3]
	ans = max(ans,res)
def rec(ind,p,l):
	if(ind == n):
		calc(l)
		return
	for i in range(p,m+1):
		l.append(i)
		rec(ind+1,i,l)
		l.pop()
n,m,Q = map(int,input().split())
q = []
for i in range(Q):
	q.append(list(map(int,input().split())))
rec(0,1,[])
print(ans)

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


max_score = 0


def search(A):
    global max_score

    if len(A) == N:
        score = 0
        for a, b, c, d in ABCD:
            if A[b - 1] - A[a - 1] == c:
                score += d
        max_score = max(score, max_score)
        return

    for a_next in range(A[-1], M + 1):
        search(A + [a_next])


for i in range(1, M + 1):
    search([i])


print(max_score)