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

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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())
    A[i] -= 1
    B[i] -= 1


def calc(X):
    score = 0
    for i in range(Q):
        if X[B[i]] - X[A[i]] == C[i]:
            score += D[i]

    return score


def solve(idx, par, X):
    if idx == N:
        return calc(X)

    ret = 0
    for i in range(par, M + 1):
        X[idx] = i
        ret = max(ret, solve(idx + 1, i, X))

    return ret


print(solve(0, 1, [0] * N))

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

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

ans0 = []


def c(L):
    if len(L) == n:
        ans = 0
        for i in range(q):
            if L[A[i][1]-1] - L[A[i][0]-1] == A[i][2]:
                ans += A[i][3]
        ans0.append(ans)
        
    elif len(L) == 0:
        for i in range(1, m+1):
            c([i])
    else:
        for i in range(L[-1], m+1):
            c(L + [i])

c([])
print(max(ans0))

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

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

def dfs(s):
    if len(s) == n:
        global ans
        cnt = 0
        for a, b, c, d in abcd:
            a -= 1; b -= 1
            if s[b] - s[a] == c: cnt += d
        ans = max(ans, cnt)
        return
    for i in range(s[-1], m+1):
        dfs(s + [i])

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

print(ans)

Solution (Python):
ans = []
def dfs(li):
    if len(li) == n:
        ans.append(li)
        return
    else:
        for i in range(li[-1], m + 1):
            dfs(li + [i])
 
  

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

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


res = 0
for ptn in ans:
    tmp = 0
    for a, b, c, d in info:
        a -= 1
        b -= 1
        if ptn[b] - ptn[a] == c:
            tmp += d
    res = max(res, tmp)
print(res)

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

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


def calc_score(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_score(A)
        ans = max(ans, score)

    elif len(A) == 0:
        for n in range(1, M + 1):
            dfs([n])
    else:
        for n in range(A[-1], M + 1):
            dfs(A + [n])


dfs([])
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline

ans = 0
N, M, Q = map(int, rl().split())
abcd = [list(map(int, rl().split())) for _ in range(Q)]


def calc(A):
    if len(A) == N:
        tmp = 0
        for a, b, c, d in abcd:
            if A[b - 1] - A[a - 1] == c:
                tmp += d
        global ans
        ans = max(ans, tmp)
    else:
        for i in range(A[-1], M + 1):
            calc(A + [i])


def solve():
    for i in range(1, M + 1):
        calc([i])
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
n,m,q=map(int,input().split())
from itertools import combinations_with_replacement as com
li = list(range(1,m+1))

abcds = [list(map(int,input().split()))for _ in range(q)]
ans = 0
for lis in com(li,n):
    res = 0
    for i in range(q):
        a,b,c,d = abcds[i][0],abcds[i][1],abcds[i][2],abcds[i][3]
        if lis[b-1] - lis[a-1] == c:
            res += d
    ans = max(ans,res)
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
printn = lambda x: print('\n'.join(x))

n, m, q = nm()
query = [tuple(nm()) for _ in range(q)]
def dfs(lis):
    if len(lis) >= n:
        yield lis
    else:
        v = 1 if not lis else lis[-1]
        for i in range(v, m+1):
            yield from dfs(lis + [i])

ans = -10**12
E = dfs(list())
for lis in E:
    sc = 0
    for a, b, c, d in query:
        if lis[b-1] - lis[a-1] == c:
            sc += d
    ans = max(ans, sc)
print(ans)

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

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

P = []
def dfs(dmax, now):
    if len(now) == N:
        P.append(now)
        return
    for n in range(dmax, M+1):
        dfs(n, now+[n])
dfs(1, [])
ans = 0
for A in P:
    score = 0
    for a, b, c, d in ABCD:
        if A[b-1] - A[a-1] == c:
            score += d
    ans = max(ans, score)

print(ans)

Solution (Python):
import itertools

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

abcd=[]

for i in range(Q):
    abcd.append([int(j) for j in input().split(" ")])




def score(A):
    retval=0
    for i in range(Q):
        a,b,c,d=abcd[i]
        if A[b-1]-A[a-1]==c:
            retval+=d
    return retval

retval=0
for iter in itertools.combinations_with_replacement([i for i in range(1,M+1)],N):
    retval=max(score(sorted(iter)),retval)

print(retval)

Solution (Python):

import sys


def solve(N: int, M: int, Q: int, a: "List[int]", b: "List[int]", c: "List[int]", d: "List[int]"):
    res = 0

    def rec(A):
        nonlocal res
        if len(A) == N:
            ans = 0
            for i in range(Q):
                if A[b[i]-1] - A[a[i]-1] == c[i]:
                    ans += d[i]
            res = max(res, ans)
            return

        last_max = 1 if len(A) == 0 else A[-1]

        for i in range(last_max, M+1):
            rec(A + [i])

    rec([])
    print(res)

    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 = map(int, input().split())
ABCD = [list(map(int, input().split())) for _ in range(q)]
ans = 0
for i1 in range(1, m+1):
    for i2 in range(i1, m+1):
        for i3 in range(i2, m+1):
            for i4 in range(i3, m+1):
                for i5 in range(i4, m+1):
                    for i6 in range(i5, m+1):
                        for i7 in range(i6, m+1):
                            for i8 in range(i7, m+1):
                                for i9 in range(i8, m+1):
                                    for i10 in range(i9, m+1):
                                        temp = 0
                                        A = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        for a, b, c, d in ABCD:
                                            if A[b-1] - A[a-1] == c:
                                                temp += d
                                        ans = max(ans, temp)
print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
n, m, q = map(int, input().split())
reqs = [list(map(int, input().split())) for _ in range(q)]

ans = 0
for i in range(1<<(n+m-1)):
	if bin(i).count("1") != n:
		continue
	l = []
	tmp = 1
	for j in range(n+m-1):
		if (i>>j) & 1:
			l.append(tmp)
		else:
			tmp += 1
	res = 0
	for a, b, c, d in reqs:
		if l[b-1] - l[a-1] == c:
			res += d
	ans = max(ans, res)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, m, q = map(int,input().split())
    ABCD = [None] * q
    for i in range(q):
        a, b, c, d = map(int,input().split())
        ABCD[i] = (a, b, c, d)

    def dfs(A):
        
        if len(A) == n + 1: 
            
            score = 0
            for a, b, c, d in ABCD:
                if A[b] - A[a] == c:
                    score += d
            return score
        
        res = -INF
        for i in range(A[-1], m + 1):
            res = max(res, dfs(A + [i]))
        return res

    print(dfs([1]))
resolve()

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

w = [0]*n
res = 0
def dfs(x, y):
    global w, res
    if x == n:
        tmp = 0
        for a, b, c, d in e:
            if w[b-1]-w[a-1] == c: tmp += d
        res = max(res, tmp)
        return
    for i in range(y, m+1):
        w[x] = i
        dfs(x+1, i)

dfs(0, 1)
print(res)

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

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

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

    ret = 0
    for n in range(A[-1], M+1):
        ret = max(ret, dfs(i + 1, A + [n]))
    return ret

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

print(ans)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,q = inpm()
    ans = 0
    abcd = []
    for _ in range(q):
        a,b,c,d = inpm()
        abcd.append((a,b,c,d))
    for e in itertools.combinations_with_replacement(range(m),n):
        cnt = 0
        for i in range(q):
            [a,b,c,d] = abcd[i]
            if e[b-1] - e[a-1] == c:
                cnt += d
        ans = max(ans,cnt)
    print(ans)
if __name__ == "__main__":
    main()

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

ans = 0
A = [0]*N
def f(p):
  global ans
  if p>=N:
    x = 0
    for i in range(Q):
      if A[b[i]]-A[a[i]]==c[i]:
        x += d[i]
    ans = max(ans, x)
  else:
    for i in range(1 if p==0 else A[p-1], M+1):
      A[p] = i
      f(p+1)
f(0)
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(q)]
ans=0
for com in combinations_with_replacement(range(m),n):
	t=0
	for a,b,c,d in L:
		if com[b-1]-com[a-1]==c:
			t+=d
	if t>ans:
		ans=t
print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def f(A):
        res = 0
        for a,b,c,d in g:
            if A[b] == A[a]+c:
                res += d
        return res

    n,m,q = LI()
    g = LIR(q)
    for i in range(q):
        g[i][0] -= 1
        g[i][1] -= 1
    l = [([i],i) for i in range(1,m+1)]
    for i in range(n-1):
        l = [(x+[j], j) for (x,y) in l for j in range(y,m+1)]
    ans = 0
    for A,_ in l:
        s = f(A)
        if ans < s:
            ans = s
    print(ans)
    return


if __name__ == "__main__":
    solve()

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

import itertools

ans = 0
for comb in itertools.combinations_with_replacement(list(range(1, m + 1)), n):
    l = list(comb)
    l.sort()
    tmp = 0

    for a, b, c, d in abcd:
        a -= 1
        b -= 1

        if l[b] - l[a] == c:
            tmp += d

    ans = max(ans, tmp)

print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M,Q=MI()
    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]=MI()
        
    import itertools
    ans=0
    
    
    
    for ite in itertools.combinations_with_replacement(range(1,M+1), N):
        temp=0
        for i in range(Q):
            if ite[b[i]-1]-ite[a[i]-1] == c[i]:
                temp+=d[i]
        ans=max(ans,temp)
        
    print(ans)
    
    
    
main()

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

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

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, m, q = na()
cs = []
for i in range(q):
    cs.append(na())

def dfs(pos, a, m, cs):
    if pos == len(a):
        sc = 0
        for co in cs:
            if a[co[1]-1] - a[co[0]-1] == co[2]:
                sc += co[3]
        return sc

    ans = 0
    low = 1 if pos == 0 else a[pos-1]
    for i in range(low, m+1):
        a[pos] = i
        ans = max(ans, dfs(pos+1, a, m, cs))
    return ans

print(dfs(0, [0] * n, m, cs))