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())
res = 0

def dfs(L: list):
    global res
    A = L[::]
    if len(A) == N + 1:
        now = 0
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                now += d[i]
        res = max(res, now)
        
        return
    
    A.append(A[-1])
    while A[-1] <= M:
        dfs(A)
        A[-1] += 1
    
a, b, c, d = [], [], [], []
for _ in range(Q):
    _a, _b, _c, _d = map(int, input().split())
    a.append(_a)
    b.append(_b)
    c.append(_c)
    d.append(_d)

dfs([1])
print(res)

Solution (Python):


from collections import deque
n,m,q = map(int,input().split())
l = [list(map(int,input().split())) for i in range(q)]
a,b,c,d = [list(i) for i in zip(*l)]

queue = deque([[1]])
ans = 0

while queue:
    
    x = queue.popleft()
    
    if len(x) == n:
        s = 0
        
        for i in range(q):
            if x[b[i]-1] - x[a[i]-1] == c[i]:
                s += d[i]
        ans = max(ans,s)
    else:
        
        
        
        for j in range(x[-1],m+1):
            y = x + [j]
            queue.append(y)
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())
s = [1]*n
mx = 0
while True:
  sc = 0
  for i in range(q):
    if s[b[i]-1]-s[a[i]-1] == c[i]:
      sc += d[i]
  mx = max(mx,sc)
  s[n-1] += 1
  if s[n-1]>m:
    s[n-2]+=1
    for k in range(n-2):
      if s[n-k-2]>m:
        s[n-k-3]+=1
    for i in range(1,n):
      if s[i]>m:
        s[i]=s[i-1]
  if s[0]>m:
    break
print(mx)

Solution (Python):
N,M,Q = map(int,input().split())
abcd_array = []
for i in range(Q):
    abcd = list(map(int,input().split()))
    abcd_array.append(abcd)
max_point = 0
for a in range(1,M+1):
    for b in range(a,M+1):
        for c in range(b,M+1):
            for d in range(c,M+1):
                for e in range(d,M+1):
                    for f in range(e,M+1):
                        for g in range(f,M+1):
                            for h in range(g,M+1):
                                for i in range(h,M+1):
                                    As = [1,a,b,c,d,e,f,g,h,i]
                                    point = 0
                                    for j in range(Q):
                                        if As[abcd_array[j][1]-1] - As[abcd_array[j][0]-1] == abcd_array[j][2]:
                                            point += abcd_array[j][3]
                                        if j == Q-1 and max_point < point:
                                            max_point = point
print(max_point)

Solution (Python):
from collections import deque

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

ptn = deque([])
for i in range(M):
  ptn.append([i])
while len(ptn) > 0:
  p = ptn.pop()
  if len(p) < N:
    for i in range(p[-1], M):
      ptn.append(p+[i])
  else:
    patterns.append(p)
answer = 0
for p in patterns:
  point = 0
  for a, b, c, d in queries:
    if p[b-1]-p[a-1] == c:
      point += d
  answer = max(answer, point)
print(answer)

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)
  
from collections import deque
que = deque([[1]])
M = 0

while que:
  
  lst = que.popleft()
  if len(lst) == n:
    s = 0
    for i in range(q):
      if lst[B[i]] - lst[A[i]] == C[i]:
        s += D[i]
    if M < s:
      M = s
      
  else:    
    for j in range(lst[-1],m+1):
      lst2 = lst +[j]
      que.append(lst2)
    
print(M)

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

from itertools import combinations_with_replacement as comb_rplc
answer = 0

for seq in comb_rplc(range(1,M+1),N):
    candi = 0
    
    for i in range(Q):
        if seq[B[i]-1]-seq[A[i]-1] == C[i]:
            candi += D[i]
    answer = max(candi,answer)
print(answer)

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())
l=range(1,M+1)

i=0;D=[]
for v in itertools.combinations_with_replacement(l, N):
  D.append(0)
  for j in range(Q):
    if v[b[j]-1]-v[a[j]-1]==c[j]:
      D[i]+=d[j]
  i+=1
print(max(D))

Solution (Python):
import itertools
from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
  
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())
l=range(1,M+1)


h=combinations_count(M+N-1, N)
H=[0]*h;i=0
for v in itertools.combinations_with_replacement(l, N):
    H[i]=v
    i+=1

D=[0 for j in range(h)]

for i in range(h):
  for j in range(Q):
    if H[i][b[j]-1]-H[i][a[j]-1]==c[j]:
      D[i]+=d[j]
  
print(max(D))

Solution (Python):
import sys
import itertools

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)
    B.append(b)
    C.append(c)
    D.append(d)

num = list(range(1,M+1))
ans = 0
for tpl in itertools.combinations_with_replacement(num,N):
    point = 0
    for i in range(Q):
        if tpl[B[i]-1] - tpl[A[i]-1] == C[i]:
            point += D[i]
    
    ans = max(ans,point)

print(ans)

Solution (Python):
import copy

def gen_mono_inc_seqs(N, M, cur_list, cur_len):
    if cur_len == N:
        return cur_list

    result = []
    for l in cur_list:
        last_val = l[len(l)-1]
        for i in range(last_val, M+1):
            tmp = copy.copy(l)
            tmp.append(i)
            result.append(tmp)

    return gen_mono_inc_seqs(N, M, result, cur_len+1)


def mono_inc_seqs(N, M):
    l = [ [i] for i in range(1, M+1) ]
    return gen_mono_inc_seqs(N, M, l, 1)

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_, b_, c_, d_ = map(int, input().split())
    a[i], b[i], c[i], d[i] = a_, b_, c_, d_

max_result = -1
seqs = mono_inc_seqs(N, M)
for seq in seqs:
    tmp = 0
    for i in range(Q):
        if seq[b[i]-1] - seq[a[i]-1] == c[i]:
            tmp += d[i]
    max_result = max(max_result, tmp)

print(max_result)

Solution (Python):
import sys

n,m,q = map(int,input().split())
score = {}
for i in range(1,10):
  for j in range(2,11):
    score[(i,j)] = [0 for k in range(10)]
    
for i in range(q):
  a,b,c,d = map(int,input().split())
  score[(a,b)][c] = d


total = []
dic = {}
for i in range(m):
  dic[(i,)] = score[(1,2)][i]
total.append(dic)

if n == 2:
  print(max(score[(1,2)]))
  sys.exit()

M = []
for i in range(2,n):
  Max = 0
  d = {}
  for k in range(m):
    for tup in total[-1].keys():
      s = total[-1][tup]
      if tup[-1] <= k:
        for j in range(1,i):
          s += score[(j+1,i+1)][k-tup[j-1]] 
        s += score[(1,i+1)][k]  
        ky = tup + (k,)
        d[ky] = s
        if s > Max:
          Max = s
  total.append(d)
  M.append(Max)

print(M[-1])

Solution (Python):



import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


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

    print(dfs([1]))


def dfs(L):
    if len(L) == N:
        score = 0
        for abcd in ABCD:
            a, b, c, d = abcd
            if L[b-1] - L[a-1] == c:
                score += d
        return score

    ans = 0
    for i in range(L[-1], M+1):
        NL = L + [i]
        ans = max(ans, dfs(NL))

    return ans


if __name__ == "__main__":
    
    resolve()

Solution (Python):



import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


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

    T = []
    func([1], T)

    ans = 0
    for t in T:
        score = 0
        for abcd in ABCD:
            a, b, c, d = abcd
            if t[b-1] - t[a-1] == c:
                score += d
        ans = max(ans, score)
    print(ans)


def func(L, T):
    if len(L) == N:
        T.append(L)
        return

    for i in range(L[-1], M+1):
        NL = L + [i]
        func(NL, T)


if __name__ == "__main__":
    
    resolve()

Solution (Python):



from itertools import combinations_with_replacement as cwr
import sys
from io import StringIO
import unittest
sys.setrecursionlimit(100000)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 4 3
1 3 3 100
1 2 2 10
2 3 2 10"""
        output = """110"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """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"""
        output = """357500"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10 10 1
1 10 9 1"""
        output = """1"""
        self.assertIO(input, output)


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

    T = []
    func([1], T)

    ans = 0
    for t in cwr(range(1, M+1), N):
        score = 0
        for abcd in ABCD:
            a, b, c, d = abcd
            if t[b-1] - t[a-1] == c:
                score += d
        ans = max(ans, score)
    print(ans)


def func(L, T):
    if len(L) == N:
        T.append(L)
        return

    for i in range(L[-1], M+1):
        NL = L + [i]
        func(NL, T)


if __name__ == "__main__":
    
    resolve()

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

ans = 0
for seq in cwr(range(1, M+1), N):
    sco = 0
    for i in range(Q):
        if seq[req[i][1]-1] - seq[req[i][0]-1] == req[i][2]:
            sco += req[i][3]
    s = max(ans, sco)
    ans = s
print(ans)

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

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

def gen():
    seq = [[1]]
    for _ in range(N-1):
        new_seq = []
        for prefix in seq:
            for i in range(prefix[-1], M+1):
                new_seq.append(prefix+[i])
        seq = new_seq
    return seq

ans = 0
for A in gen():
    cand = 0
    for a, b, c, d in rules:
        if A[b]-A[a] == c:
            cand += d
    ans = max(ans, cand)
print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import combinations_with_replacement
import numpy as np
def main():
    n, m, q = map(int, input().split())
    A = np.array(list(combinations_with_replacement(range(1, m + 1), n)))
    numA = len(A)
    score = np.zeros(numA, np.int32)
    ma = map(int, read().split())
    for a, b, c, d in zip(ma, ma, ma, ma):
        a -= 1
        b -= 1
        eachA_is_equalOrNot = A[:, b] - A[:, a] == c
        score += d * eachA_is_equalOrNot
        
    print(score.max())

if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import combinations_with_replacement
def main():
    n, m, q = map(int, input().split())
    qs = []
    for _ in range(q):
        abcd = tuple(map(int, input().split()))
        qs.append(abcd)
    A = tuple(combinations_with_replacement(range(1, m+1), n))
    r = 0
    for Ae in A:
        t0 = 0
        for qe in qs:
            if Ae[qe[1]-1] - Ae[qe[0]-1] == qe[2]:
                t0 += qe[3]
        r = max(r, t0)
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
N, M, Q = map(int, input().split())
a = []
b = []
c = []
d = []
for _ in range(Q):
    ad, bd, cd, dd = map(int, input().split())
    a.append(ad-1)
    b.append(bd-1)
    c.append(cd)
    d.append(dd)
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 as com

N,M,Q=map(int,input().split())
query=[tuple(map(int,input().split())) for _ in [0]*Q]

res=0
for p in com(list(range(N+M-1)),M-1):
    m=1
    A=[]
    for i in range(N+M-1):
        if i in p:
            m+=1
        else:
            A.append(m)
    tmpres=0
    for a,b,c,d in query:
        if A[b-1]-A[a-1]==c:
            tmpres+=d

    res=max(tmpres,res)
print(res)

Solution (Python):
def dfs(cnt, lowest, lst):
    global ans
    if cnt > n:
        return
    for i in range(lowest, m+1):
        lst.append(i)
        dfs(cnt+1, i, lst)
        lst.pop()
    if cnt == n:
        num = 0
        for i in range(q):
            a, b, c, d = ab[i]
            if lst[b-1] - lst[a-1] == c:
                num += d
        ans = max(num, ans)

n,m,q = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0
dfs(0, 1, [])

print(ans)

Solution (Python):
def dfs(lst):
    global ans
    if len(lst) > n:
        return
    lowest = 1
    if lst != []:
        lowest = lst[-1]
    for i in range(lowest, m+1):
        lst.append(i)
        dfs(lst)
        lst.pop()
    if len(lst) == n:
        cnt = 0
        for i in range(q):
            a, b, c, d = ab[i]
            if lst[b-1] - lst[a-1] == c:
                cnt += d
        ans = max(cnt, ans)

n,m,q = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(q)]
ans = 0
dfs([])

print(ans)

Solution (Python):
from itertools import combinations_with_replacement as combi

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

a = [0] * 55
b = [0] * 55
c = [0] * 55
d = [0] * 55

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

candidate = combi(range(1, M+1), N)

ans = 0

for A in candidate:
    score = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            score += d[i]

    ans = max(ans, score)

print(ans)

Solution (Python):
from collections import deque
def calc(seq):
  score = 0
  for a,b,c,d in array:
    if seq[b-1] - seq[a-1] == c:
      score += d
  return score
  
N,M,Q = map(int,input().split())
array = [ 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
n,m,q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

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

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

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

Solution (Python):
import copy
Z=[]

def dfs(A,n,m):
    global Z
    if len(A)==n:
        Z.append(copy.deepcopy(A))
        return
    
    first = A[-1] if len(A)>0 else 1
    
    for i in range(first, m+1):
        
        A.append(i)
        
        dfs(A,n,m)
        A.pop()
    

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

dfs([],n,m)


A=[]
B=[]
C=[]
D=[]

for _ in range(q):
    a,b,c,d = map(int,input().split()) 
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
    
ans = 0    
for z in Z:
    score=0
    for i in range(q):
        if z[B[i]-1] - z[A[i]-1] == C[i]:
            score += D[i]
            
    ans=max(ans,score)
        
    
print(ans)

Solution (Python):
from itertools import combinations_with_replacement as comb_rplc
N,M,Q = map(int,input().split())
array = [ 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 array:
    if seq[b-1] - seq [a-1] == c:
      score += d
  ans = max(score,ans)
print(ans)

Solution (Python):
import itertools
n,m,q=list(map(int,input().split()))
abcd=[[] for i in range(q)]
for i in range(q):
    abcd[i]=list(map(int,input().split()))
ans=0
l=list(itertools.combinations_with_replacement([a for a in range(1,m+1)],n))
x=(len(l))
for i in range(x):
    e=l[i]
    
    wa=0
    for t in range(q):
        if e[abcd[t][1]-1]-e[abcd[t][0]-1]==abcd[t][2]:
            wa+=abcd[t][3]
    ans=max(ans,wa)
print(ans)

Solution (Python):

import sys
from itertools import chain







def solve(
    N: int, M: int, Q: int, ABCD: "List[(int,int,int,int)]",
):
    def dfs(A, l, r, n):
        if n > 0:
            max_score = 0
            for Ai in range(l, r + 1):
                A.append(Ai)
                score = dfs(A, Ai, r, n - 1)
                if score > max_score:
                    max_score = score
                A.pop()
            return max_score
        else:
            score = 0
            for a, b, c, d in ABCD:
                if A[b - 1] - A[a - 1] == c:
                    score += d
            return score

    return dfs([], 1, M, N)


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    N = int(next(tokens))  
    M = int(next(tokens))  
    Q = int(next(tokens))  
    ABCD = []
    for i in range(Q):
        a = int(next(tokens))
        b = int(next(tokens))
        c = int(next(tokens))
        d = int(next(tokens))
        ABCD.append((a, b, c, d))
    answer = solve(N, M, Q, ABCD)
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import combinations_with_replacement

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

cands = []
for i in combinations_with_replacement(list(range(1,m+1)),n):
    cands.append(i)

maxi = 0
for cand in cands:
    score = 0
    for condition in conditions:
        if cand[condition[1]-1] - cand[condition[0]-1]  == condition[2]:
            score += condition[3]
    if score > maxi:
        maxi = score
print(maxi)

Solution (Python):
from itertools import combinations_with_replacement as cwr
N,M,Q=map(int,input().split())
ABCD=[]
for _ in range(Q):
    ABCD.append(list(map(int,input().split())))
maxscore=0
for comb in cwr(range(1,M+1),N):
    score=0
    for row in ABCD:
        if comb[row[1]-1]-comb[row[0]-1]==row[2]:
            score+=row[3]
    maxscore=max(maxscore,score)
print(maxscore)

Solution (Python):
import bisect,collections,copy,itertools,math,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())
def main():
    n,m,q = LI()
    require = [LI() for _ in range(q)]
    itr = itertools.combinations_with_replacement(list(range(1,n+2)),m-1)     
    ans = 0
    for i in itr:
        lst = [0 for _ in range(n+2)]
        lst[0] = 1
        cnt = 0
        for j in i:
            lst[j] += 1
        lst = list(itertools.accumulate(lst))
        for re in require:
            if lst[re[1]]-lst[re[0]]==re[2]:
                cnt += re[3]
        ans = max(cnt,ans)
    print(ans)

main()

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

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
A = []
def rec(itr, lst):
    if itr == N:
        res = 0
        for a, b, c, d in abcd:
            if A[b-1] - A[a-1] == c:
                res += d
        return res
    else:
        res = 0
        for i in range(lst, M):
            A.append(i)
            res = max(res, rec(itr + 1, i))
            A.pop()
        return res
print(rec(0, 0))

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

N, M, Q = map(int, input().split())
abcd = [list(map(int, input().split())) for i in range(Q)]
A = []
def rec(itr, lst):
    if itr == N:
        res = 0
        for a, b, c, d in abcd:
            if A[b-1] - A[a-1] == c:
                res += d
        return res
    else:
        res = 0
        for i in range(lst, M):
            A.append(i)
            res = max(res, rec(itr + 1, i))
            A.pop()
        return res
print(rec(0, 0))

Solution (Python):
import sys
import itertools

N, M, Q = map(int, input().split())
abcd = []
z = [x for x in range(1,M+1)]
s = 0
d = 0
for i in range(Q):
    abcd.append(list(map(int, input().split())))

for A in itertools.combinations_with_replacement(z, N):
    d = 0
    for y in abcd:
        if A[y[1]-1] - A[y[0]-1] == y[2]:
            d += y[3]
    s = max(d, s)

print(s)

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

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

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

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

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

Solution (Python):

"""
Created on Thu Sep  3 23:43:13 2020

@author: liang
"""

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

A = list()
lis = list()
ans = 0

def make_list(n,m):
    if n == N:
        A.append(lis.copy())
        return 
    for i in range(m,M+1):
        lis.append(i)
        make_list(n+1,i)
        lis.pop()

make_list(0,1)


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

for a in A:
    tmp = 0
    for c in calc:
        if a[c[1]-1] - a[c[0]-1] == c[2]:
            tmp += c[3]
    if tmp > ans:
        ans = tmp
       
print(ans)

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


big_lis = []


def dfs(string, n, m):
    if n == (N - 1):
        for i in range(m, M + 1):
            big_lis.append(string + [i])
    else:
        for i in range(m, M + 1):
            dfs(string + [i], n + 1, i)


dfs([], 0, 1)

MAX_A = 0
for small_lis in big_lis:
    D = 0
    for j in range(Q):
        if small_lis[int(lis[j][1]) - 1] - small_lis[int(lis[j][0]) - 1] == int(lis[j][2]):
            D += int(lis[j][3])
    MAX_A = max(MAX_A, D)
print(MAX_A)

Solution (Python):

import collections as cl
import sys


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 main():
    N, M, Q = MI()
    targets = [[] for i in range(Q)]
    for i in range(Q):
        target = LI()
        targets[i] = target
    ans = 0
    for i in range(1, 2**(M+N)):
        i_str = format(i, f"0{M+N-1}b")
        A = []
        tmp = 1
        for k in range(len(i_str)):
            if i_str[k] == "1":
                tmp += 1
            else:
                A.append(tmp)
        if len(A) != N:
            continue
        score = 0
        for query in targets:
            a, b, c, d = query
            if A[b-1] - A[a-1] == c:
                score += d
        ans = max(ans, score)

    print(ans)


main()

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


def dfs():
    global A
    if len(A) == N:
        return
    global ans
    if len(A) == 0:
        start = 1
    else:
        start = A[-1]
    for i in range(start, M + 1):
        A.append(i)
        dfs()
        if len(A) != N:
            A.pop()
            continue
        
        tmp_ans = 0
        for a, b, c, d in Q:
            if A[b - 1] - A[a - 1] == c:
                tmp_ans += d
        ans = max(ans, tmp_ans)
        A.pop()


dfs()
print(ans)

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

ans = 0
for a in range(M):
    for b in range(a, M):
        for c in range(b, M):
            for d in range(c, M):
                for e in range(d, M):
                    for f in range(e, M):
                        for g in range(f, M):
                            for h in range(g, M):
                                for i in range(h, M):
                                    for j in range(i, M):
                                        tmp = [a, b, c, d, e, f, g, h, i, j]
                                        tmp_ans = 0
                                        for q in range(Q):
                                                if tmp[L[q][1]-1] - tmp[L[q][0]-1] == L[q][2]:
                                                    tmp_ans += L[q][3]

                                        ans = max(ans, tmp_ans)

print(ans)

Solution (Python):
import itertools

n,m,q=map(int,input().split())
lst=[]
ans=0

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

for x in list(itertools.combinations_with_replacement(range(1,m+1),n)):
  cnt=0
  for i in lst:
    if x[i[1]-1]-x[i[0]-1]==i[2]:
      cnt+=i[3]

  ans=max(ans,cnt)


print(ans)

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

for l2 in c(range(1, M + 1), N):
    total = 0
    for i in range(Q):
        if l2[l1[i][1] - 1] - l2[l1[i][0] - 1] == l1[i][2]:
            total += l1[i][3]
    ans = max(ans, total)

print(ans)

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

ans = 0

for l2 in c(range(1, M + 1), N):
  total = 0
  for i in range(Q):
    if l2[l1[i][1] - 1] - l2[l1[i][0] - 1] == l1[i][2]:
      total += l1[i][3]
  ans = max(ans, total)

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

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

for A in itertools.combinations_with_replacement(cc, N):
    A = list(A)
    t = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            t += d[i]
    ans = max(ans, t)

print(ans)

Solution (Python):
import numpy as np
import itertools
N, M, Q = map(int, input().split())
G = []
for i in range(Q):
    a, b, c, d = map(int, input().split())
    G.append([a, b, c, d])

ans = 0

A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))

n = len(A)
score = np.zeros(n, np.int32)
for a, b, c, d in G:
    cond = A[:, b - 1] - A[:, a - 1] == c
    score += d * cond

print(score.max())