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())
A = [list(map(int,input().split())) for _ in range(Q)]

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

    max_score = 0
    for n in range(arr[i-1] if i >= 0 else 1, M+1):
        x = [arr[k] if k != i else n for k in range(N)]
        max_score = max(max_score, dfs(x,i+1))
    
    return max_score
        
print(dfs([1 for _ in range(N)]))

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

ans = []
import itertools
for A in itertools.combinations_with_replacement(range(1, M+1), N):
    tmp = 0
    for a, b, c, d in abcd:
        if A[b-1] - A[a-1] == c:
            tmp += d
    ans.append(tmp)
print(max(ans))

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

Solution (Python):
import sys

sys.setrecursionlimit(3000000)

x=10
def sol(a):
    if len(a)==10:
        tmp=0
        if max(a)<=f[1]:
            for i in w:
                if a[i[1]-1]-a[i[0]-1]==i[2]:
                    tmp+=i[3]
        ans[0]=max(ans[0],tmp)
        return
    s=a[-1] if len(a) else 1
    for i in range(s,10+1):
        a.append(i)
        sol(a)
        a.pop()

ans=[0]
n,m,q=map(int,input().split())
f=[n,m]
w=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    w.append((a,b,c,d))


sol([])
print(ans[0])

Solution (Python):
from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, M, Q = [int(x) for x in stdin.readline().rstrip().split()]
abcd = [list(map(int, stdin.readline().rstrip().split())) for _ in range(Q)]

ans = 0

nums = [i for i in range(1, M+1)]
A = list(itertools.combinations_with_replacement(nums, N))

for l in A:
    l = (0,) + l 
    tmp_ans = 0
    for a, b, c, d in abcd:
        if l[b] - l[a] == c:
            tmp_ans += d


    
    ans = max(ans, tmp_ans)

print(ans)

Solution (Python):




import numpy as np
from itertools import combinations_with_replacement










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


abcd_array = []
for i in range(Q):
    abcd = map(int, input().split())
    abcd_array.append(list(abcd))






anslist_candidates = combinations_with_replacement(range(1, M+1), N)


max_anslist_score = 0
for tmp_anslist in anslist_candidates:
    sum_d = 0

    is_valid_anslist = True
    prev_ansitem = tmp_anslist[0]
    for ansitem in tmp_anslist[1:]:
        if prev_ansitem > ansitem:
            is_valid_anslist = False
            break
    if not is_valid_anslist:
        continue

    for ai, bi, ci, di in abcd_array:
        
        
        if ((tmp_anslist[bi-1] - tmp_anslist[ai-1]) == ci):
            sum_d += di
    
    max_anslist_score = max(max_anslist_score, sum_d)

print(max_anslist_score)

Solution (Python):
from functools import lru_cache
import sys


def dfs(A,B):
    if len(A)==n:
        ans=0
        for i in num_list:
            if A[i[1]-1]-A[i[0]-1]==i[2]:
                ans+=i[3]
        B.append(ans)
        return
    for i in range(max(A),m+1):
        A.append(i)
        dfs(A,B)
        A.pop()
if __name__=="__main__":
    sys.setrecursionlimit(10000)
    n,m,q=map(int,input().split())
    num_list=[]
    ans_lst=[]
    for i in range(q):
        tmp=list(map(int,input().split()))
        num_list.append(tmp)
    a=[]
    for i in range(1,m+1):
        a.append(i)
        dfs(a,ans_lst)
        a.clear()
    print(max(ans_lst))

Solution (Python):
N,M,Q=map(int,input().split())
qs=[list(map(int,input().split()))for i in range(Q)]
from itertools import combinations_with_replacement
com=combinations_with_replacement(range(1,M+1),N)

ans=0
for A in com:
    
    tmp=0
    for a,b,c,d in qs:
        if (A[b-1]-A[a-1]==c):
            tmp+=d
    ans=max(ans,tmp)

print(ans)

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

query = []

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

res = 0


def solve(A):
    global res
    if len(A) == N:
        tmp = 0
        for q in query:
            a, b, c, d = q

            if A[b - 1] - A[a - 1] == c:
                tmp += d
        res = max(res, tmp)
        return

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


for i in range(1, M + 1):
    solve([i])
print(res)

Solution (Python):
def solve():
    N,M,Q = map(int,input().split())
    global info
    info = []
    for _ in range(Q):
        a,b,c,d = map(int,input().split())
        a -= 1
        b -= 1
        info.append([a,b,c,d])

    print(dfs(list(),M,N))

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

def calcPoint(A):
    result = 0
    for a,b,c,d in info:
        if A[b] - A[a] == c:
            result += d
    return result
                
if __name__ == '__main__':
    solve()

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

from itertools import combinations_with_replacement 
com = combinations_with_replacement(range(1,M+1),N)

ans = 0
for A in com:
    tmp = 0
    for a,b,c,d in qs:
        if (A[b-1] - A[a-1] == c): tmp += d
    ans = max(ans,tmp)
print(ans)

Solution (Python):
import itertools
n,m,q=(int(x) for x in input().split())

i = itertools.combinations_with_replacement(range(1,m+1),n)
score = 0
a,b,c,d = [0]*q,[0]*q,[0]*q,[0]*q
for j in range(q):
    a[j],b[j],c[j],d[j]=(int(x) for x in input().split())
for array in i:
    tmp = 0
    for j in range(q):
        tmp += d[j] if array[b[j]-1] - array[a[j]-1] == c[j] else 0
    score = max(tmp,score)
print(score)

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)

def dfs(A):
    if len(A) == n:  
        score = 0
        for i in range(q):
            if A[b[i]-1] - A[a[i]-1] == c[i]:
                score += d[i]
        return score

    ans = 0
    for i in range(A[-1], m+1):
        A.append(i)
        ans = max(ans, dfs(A))
        A.pop()
    return ans

print(dfs([1]))

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

a_list = []

def dfs(n, m, l):
    a = copy.copy(l)
    if a.count(0) == 0:
        a_list.append(a)
        return
    if a[0] == 0:
        for i in range(1, n+1):
            a[0] = i
            dfs(n, m, a)
        return
    for i in range(1, n):
        if a[i] == 0:
            for j in range(m-a[i-1]+1):
                a[i] = a[i-1] + j
                dfs(n, m, a)
            return

def get_score(l, score_list):
    score = 0
    for s in score_list:
        a = s[0]
        b = s[1]
        c = s[2]
        d = s[3]
        if l[b-1] - l[a-1] == c:
            score += d
    return score
dfs(n, m, [0 for _ in range(n)])

ans_list = [get_score(a, score_list) for a in a_list]
print(max(ans_list))

Solution (Python):
import itertools

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

number = []
for i in range(m):
    number.append(i+1)
a = list(itertools.combinations_with_replacement(number,n))
length = len(a)
memo = [0] * length
ans = 0

for i in range(length):
    sum = 0
    for j in range(q):
       if a[i][num[j][1]-1] - a[i][num[j][0]-1]  == num[j][2]:
            sum += num[j][3]
    ans = max(sum,ans)
print(ans)

Solution (Python):

from itertools import combinations_with_replacement

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



cmb = combinations_with_replacement([i for i in range(1, m + 1)], n)
all_array = list(cmb)
"""for i in combination_all:
    tmp = 1
    lis = []
    for j in range(len(i)):
        if i[j]:
            lis.append(tmp)
        else:
            tmp += 1
    all_array.append(lis)"""

ans = 0  
for arr in all_array:
    val = 0
    for j in range(q):
        if arr[abcd[j][1] - 1] - arr[abcd[j][0] - 1] == abcd[j][2]:
            val += abcd[j][3]
    ans = max(ans, val)
print(ans)


"""ans = 0

for i in range(2**n):
    score = 0
    emerge = []
    lis = []
    for j in range(n):
        if i>>j & j:
            if a[i] in emerge:"""

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

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

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

ans = [0]
def dfs(x,n2,m1):
  if len(x) == n2:
    score = sum(x1[3] for x1 in list1 if x[x1[1]-1]-x[x1[0]-1] == x1[2])
    if score > ans[0]:
      ans[0] = score
  else:
    for i in range(1,m1+1,1):
      if i >= x[-1]:
        dfs(x+[i],n2,m1)

dfs([1],N,M)
print(ans[0])

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-1)
    b.append(bi-1)
    c.append(ci)
    d.append(di)

def score(A):
    tmp = 0
    for j in range(Q):
        if A[b[j]] - A[a[j]] == c[j]:
            tmp += d[j]
    return tmp
    
def dfs(A):
    if len(A) == N:
        return score(A)
    Alast = A[-1] if len(A) > 0 else 1
    res = 0
    for k in range(Alast,M+1):  
        A.append(k)
        res = max(res,dfs(A))
        A.pop()
    return res

print(dfs([]))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,m,q = LI()
    aa = [LI() for _ in range(q)]
    r = 0
    for l in itertools.combinations_with_replacement(range(1,m+1), n):
        t = 0
        for a,b,c,d in aa:
            if l[b-1] - l[a-1] == c:
                t += d
        if r < t:
            r = t
    return r

print(main())

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

ans=0
def search(l):
    global ans
    if len(l)==n+1:
        score=0
        for i in range(q):
            if l[a[i][1]]-l[a[i][0]]==a[i][2]:
                score+=a[i][3]
        ans=max(ans,score)
    
    else:
        for i in range(l[-1],m+1):
            search(l+[i])

search([1])

print(ans)

Solution (Python):

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




ans = 0
for A in L:
    tmp = 0
    for i in range(Q):
        a = D[i][0]
        b = D[i][1]
        c = D[i][2]
        d = D[i][3]
        if A[b-1] - A[a-1] == c:
            tmp += d
        
        ans = max(ans,tmp)

print(ans)

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

def dfs(a):
    if len(a)==n:
        tmp=a[:]
        a_lis.append(tmp)
        return
    
    for i in range(m):
        if len(a)>0 and i<a[-1]:
            continue
        a.append(i)
        dfs(a)
        a.pop()

cnt=0        
n,m,q=map(int,input().split())
lis=[[int(i) for i in input().split()]for i in range(q)]
a_lis=[]

dfs([])
ans=0
for i in a_lis:
    score=0
    for a,b,c,d in lis:
        if i[b-1]-i[a-1]==c:
            score+=d
    ans=max(ans,score)
print(ans)

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

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

from itertools import combinations

a = [i for i in range(1, n+m+1)]
As = list(combinations(a, n))
ans = []

for a in As:
    A = []
    now = 0
    for i in range(1, n+m+1):
        if i in a:
            A.append(now)
        else:
            now += 1
    if A[0] == 0:
        continue
    D = 0
    for abc in abcd:
        if A[abc[1]] - A[abc[0]] == abc[2]:
            D += abc[3]
    ans.append(D)
print(max(ans))

Solution (Python):

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

ans = 0

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

def dfs(A):
  global ans

  if len(A) == n:
    score = calc(A)
    ans = max(ans, score)

  elif len(A) == 0:
    for i in range(1, m+1):
      dfs([i])

  else:
    for i in range(A[-1], m+1):
      dfs(A + [i])

dfs([])
print(ans)

Solution (Python):
nums = [int(e) for e in input().split()]
n = nums[0]
m = nums[1]
q = nums[2]

max_score = 0

total_qs = []

for i in range(q):
    qs = [int(e) for e in input().split()]
    total_qs += [qs]



def calc_score(a2):
    score = 0

    for tmp_q in total_qs:
        if a2[tmp_q[1]] - a2[tmp_q[0]] == tmp_q[2]:
            score += tmp_q[3]

    return score





def dfs(a1):
    global max_score
    if len(a1) == n+1:
        
        tmp_score = calc_score(a1)
        if max_score < tmp_score:
            max_score = tmp_score
        return

    a1.append(a[len(a1) - 1])
    while a1[len(a1) - 1] <= m:
        dfs(a1)
        a1[len(a1) - 1] += 1

    a1.pop(-1)
    return




a = [1]

dfs(a)

print(max_score)

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

ans = 0
for A in itertools.combinations_with_replacement(range(1,M+1),N):
    cnt = 0
    for q in range(Q):
        if A[abcd[q][1] - 1] - A[abcd[q][0] - 1] == abcd[q][2]:
            cnt += abcd[q][3]
    ans = max(ans,cnt)

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())
import itertools
ans=0
for A in itertools.combinations_with_replacement(range(1,M+1),N):
  A_=list(A)
  s=0
  
  for i in range(Q):
    if A_[b[i]-1]-A_[a[i]-1]==c[i]:
      s+=d[i]
    ans=max(ans,s)
print(ans)

Solution (Python):


import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from itertools import combinations_with_replacement

def main():
    n, m, q = list(map(int, input().strip().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] = list(map(int, input().strip().split()))
        a[i] -= 1
        b[i] -= 1
    ans = 0
    for v in combinations_with_replacement(range(1, m+1), n):
        s = 0
        for i in range(q):
            if v[b[i]] - v[a[i]] == c[i]:
                s += d[i]
        ans = max(ans, s)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N, M, Q = map(int, input().split())
req = [list(map(int, input().split())) for i in range(Q)]
maxi = 0
def dfs(A):
  global maxi
  
  if len(A) == N:  
    ans = 0
    for i in range(Q):
      if A[req[i][1]-1] - A[req[i][0]-1] == req[i][2]:
        ans += req[i][3]
        
    maxi = max(maxi, ans)
    return
      
  if len(A) == 0:
    for v in range(1, M+1):
      A.append(v)
      dfs(A)
      A.pop()
      
  else:    
    for v in range(A[-1], M+1):
      A.append(v)
      dfs(A)
      A.pop() 

dfs([])
print(maxi)

Solution (Python):
import itertools
n,m,q = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(q)]
ans = 0
list_ = list(itertools.combinations_with_replacement(range(1, m + 1), n))
for i in list_:
    tmp = 0
    for a,b,c,d in arr:
        if (i[b-1] - i[a-1]==c):
            tmp+=d
    ans=max(ans,tmp)
print(ans)

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

ans = []


def dfs(l):
    if len(l) == N:
        tmp = 0
        for q in query:
            if (l[q[1]-1] - l[q[0]-1]) == q[2]:
                tmp += q[3]
        ans.append(tmp)
        return
    prev = l[-1] if len(l) > 0 else 1
    for v in range(prev, M+1):
        l.append(v)
        dfs(l)
        l.pop()


dfs([])
print(max(ans))

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

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

def dfs(a):
    if len(a)==n:
        return point(a)
    res = 0
    prev_last = a[-1] if len(a) > 0 else 1
    for i in range(prev_last, m+1):
        a.append(i)
        res = max(res, dfs(a))
        a.pop()
    return res

print(dfs([]))

Solution (Python):
import itertools
n, m, q = map(int, input().split())
A = itertools.combinations_with_replacement(range(1, m+1), n)
quads = [[int(i) for i in input().split()] for j in range(q)]
max_p = 0
for a in A:
    p = 0
    for quad in quads:
        if a[quad[1] - 1] - a[quad[0] - 1] == quad[2]:
            p += quad[3]
    if max_p < p:
        max_p = p
print(max_p)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)
def calc(a, n, m, arr):
    if len(a) == n:
        val = 0
        for p, q, c, d in arr:
            if a[p-1] + c == a[q-1]:
                val += d
        return val
    else:
        val = 0
        for i in range(a[-1], m+1):
            a.append(i)
            val = max(val, calc(a, n, m, arr))
            a.pop(-1)
        return val

def main():
    n, m, q = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(q)]
    a = [1]
    print(calc(a, n, m, arr))

if __name__ == "__main__":
    main()

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

Solution (Python):


import sys

import itertools






def dfs(A):
    """
    dfs([1]) で使用。index 1 からが本来求めたい数列になる
    """
    global ans
    if len(A) == n+1:
        
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return
    else:
        
        
        
        
        A = A + [A[-1]]
        
        
        
        while A[-1] <= m:
            
            dfs(A)
            A[-1] += 1



def dfs2(i):
    global ans
    for j in range(num[i-1], m):
        num[i] = j
        if i == n:
            print(num)
            now = 0
            for k in range(q):
                if num[b[k]] - num[a[k]] == c[k]:
                    now += d[k]
            ans = max(ans, now)
        else:
            dfs2(i+1)

def solve_combinations_with_replacement(n, m):
    def update_ans(A):
        global ans
        now = 0
        for j in range(q):
            if A[b[j]-1] - A[a[j]-1] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return

    global ans
    it = [i for i in range(m)]
    for A in itertools.combinations_with_replacement(it, n):
        update_ans(A)


n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
ans = 0

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)

dfs([1])






print(ans)

Solution (Python):





import sys




def dfs(A):
    global ans
    if len(A) == n+1:
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return
    else:
        
        A = A + [A[-1]]
        while A[-1] <= m:
            
            dfs(A)
            A[-1] += 1

def dfs_no_mutation(original):
    global ans
    A = original[:]
    if len(A) == n+1:
        now = 0
        for j in range(q):
            if A[b[j]] - A[a[j]] == c[j]:
                now += d[j]
        ans = max(ans, now)
        return
    else:
        A.append(A[-1])
        while A[-1] <= m:
            print(A)
            dfs(A)
            A[-1] += 1


def comb_with_replacement(A, n, m):
    global lists
    if len(A) == n+1:
        lists.append(A)
    else:
        A.append(A[-1])
        while A[-1] <= m:
            comb_with_replacement(A, n, m)
            A[-1] += 1



def dfs2(i):
    global ans
    for j in range(num[i-1], m):
        num[i] = j
        if i == n:
            print(num)
            now = 0
            for k in range(q):
                if num[b[k]] - num[a[k]] == c[k]:
                    now += d[k]
            ans = max(ans, now)
        else:
            dfs2(i+1)


n, m, q = map(int, input().split())
a, b, c, d = [], [], [], []
ans = 0

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)

dfs([1])


num = [0] * (n+1)





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):
import sys
from itertools import combinations_with_replacement
input = sys.stdin.readline
 
 
def readstr():
    return input().strip()
 
 
def readint():
    return int(input())
 
 
def readnums():
    return map(int, input().split())
 
 
def readstrs():
    return input().split()
 
 
N, M, Q = readnums()
num_list = [list(readnums()) for _ in range(Q)]
 
ans = 0
for v in combinations_with_replacement(range(1, M + 1), N):
    val = 0
    for n in num_list:
        if v[n[1] - 1] - v[n[0] - 1] == n[2]:
            val += n[3]
    ans = max(ans, val)
 
print(ans)

Solution (Python):
import itertools

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


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


for comb in itertools.combinations_with_replacement(R, N):
    temp = 0
    for abcd in ABCD:
        a, b, c, d = abcd
        if comb[b-1] - comb[a-1] == c:
            temp += d
    if temp >= ans:
        ans = temp

    

print(ans)

Solution (Python):
import numpy as np
import math
import scipy
import itertools

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

def dfs(arr):
    if len(arr) == n:
        return score(arr)
    last = arr[-1] if len(arr) > 0 else 0
    res = 0
    for i in range(last, m):
        arr.append(i)
        res = max(res, dfs(arr))
        arr.pop()
    return res

def solve():
    global a, b, c, d, n, m, q
    n, m, q = map(int, input().split())
    a, b, c, d = [0]*q, [0]*q, [0]*q, [0]*q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
    print(dfs([]))
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
def main():
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]
    score = 0

    def dfs(l, **kwargs):
        N = kwargs['N']
        M = kwargs['M']
        ABCD = kwargs['ABCD']

        
        if judge_end(l, N=N):
            nonlocal score
            tmp_score = calc_score(l, ABCD=ABCD)
            score = max(tmp_score, score)
            return
        else:
            
            nexts = listup_next(l[-1], M=M)
            for x in nexts:
                dfs(l+[x], N=N, M=M, ABCD=ABCD)

    def judge_end(l, **kwargs):
        N = kwargs['N']
        return len(l) == N

    def calc_score(l, **kwargs):
        ABCD = kwargs['ABCD']
        s = 0
        for a, b, c, d in ABCD:
            if l[b-1] - l[a-1] == c:
                s += d
        return s

    def listup_next(now, **kwargs):
        m = now
        M = kwargs['M']
        return range(m, M+1)

    for i in range(1, M+1):
        dfs([i], N=N, M=M, ABCD=ABCD)
    print(score)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]
    score = 0

    def dfs(l, N, M, ABCD):
        
        if judge_end(l, N):
            nonlocal score
            tmp_score = calc_score(ABCD, l)
            score = max(tmp_score, score)
            return
        else:
            
            nexts = listup_next(l[-1], M)
            for x in nexts:
                dfs(l+[x], N, M, ABCD)

    def judge_end(l, N):
        return len(l) == N

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

    def listup_next(m, M):
        return range(m, M+1)

    for i in range(1, M+1):
        dfs([i], N, M, ABCD)
    print(score)


if __name__ == "__main__":
    main()

Solution (Python):
score = 0
def main():

    N, M, Q = map(int, input().split())
    ABCD = [list(map(int, input().split())) for i in range(Q)]
    global score
    for i in range(1, M+1):
        dfs([i], N, M, ABCD)
    print(score)


def dfs(l, N, M,ABCD):
    
    if judge_end(l, N):
        global score
        tmp_score = calc_score(ABCD, l)
        score = max(tmp_score, score)
        return
    else:
        
        nexts = listup_next(l[-1], M)
        for x in nexts:
            dfs(l+[x], N, M, ABCD)


def judge_end(l, N):
    return len(l) == N


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


def listup_next(m, M):
    return range(m, M+1)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
import math
import scipy
import itertools

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

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

def solve():
    global a, b, c, d, n, m, q
    n, m, q = map(int, input().split())
    a, b, c, d = [0]*q, [0]*q, [0]*q, [0]*q
    for i in range(q):
        a[i], b[i], c[i], d[i] = map(int, input().split())
    print(dfs([]))
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):


def dfs(l,N,M):
    
    if judge_end(l,N):
        global score
        
        tmp_score = calc_score(ABCD,l)
        score = max(tmp_score, score)
        return
    else:
        
        nexts = listup_next(l[-1], M)
        for x in nexts:
            dfs(l+[x],N,M)


def judge_end(l,N):
    return len(l)==N


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


def listup_next(m, M):
    return range(m,M+1)

N,M,Q = map(int, input().split())
ABCD = [list(map(int, input().split())) for i in range(Q)]
score=0
for i in range(1, M+1):
  dfs([i], N,M)
print(score)

Solution (Python):


from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

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

com = combinations_with_replacement(range(1, M+1), N)

ma = 0
scores = []
for i in com:
    score = 0
    for j in abcd:
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            score += j[3]
    if score > ma:
        ma = score
print(ma)