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):
from itertools import combinations
n, m, q = map(int, input().split())
queries = []
for i in range(q):
    a, b, c, d = map(int, input().split())
    queries.append((a-1, b-1, c, d))


ans = 0
for i, comb in enumerate(combinations(range(n+m-2), r=n-1)):
    
    A = [1] * n
    idx = 0
    for i in range(n+m-2):
        if i in comb:
            idx += 1
            A[idx] = A[idx-1]
        else:
            A[idx] += 1

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

print(ans)

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

for A_9 in range(1,M + 1):
  for A_8 in range(1,A_9 + 1):
    for A_7 in range(1,A_8 + 1):
      for A_6 in range(1,A_7 + 1):
        for A_5 in range(1,A_6 + 1):
          for A_4 in range(1,A_5 + 1):
            for A_3 in range(1,A_4 + 1):
              for A_2 in range(1,A_3 + 1):
                for A_1 in range(1,A_2 + 1):
                  A = [A_1,A_2,A_3,A_4,A_5,A_6,A_7,A_8,A_9,M]
                  d = 0
                  for i in range(Q):
                    a = Query[i][0] - 1
                    b = Query[i][1] - 1
                    if A[b] - A[a] == Query[i][2]:
                      d += Query[i][3]
                      if d > MAX:
                        MAX = d         
      
      
           
print(MAX)

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

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

l_tensu = 0
for subset in itertools.combinations_with_replacement(A_full, N):
    tensu = 0

    A = list(subset)
    for i in range(Q):
        a = List[i][0] - 1
        b = List[i][1] - 1
        c = List[i][2]
        d = List[i][3]
        if (A[b] - A[a] == c):
            tensu += d
    if(tensu > l_tensu):
        l_tensu = tensu
    
print(l_tensu)

Solution (Python):
import itertools

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

for i in range(Q):
	series.append(list(map(int,input().split())))

A = [x for x in range(1,M+1)]

max_score = 0
for a in itertools.combinations_with_replacement(A,N):
	score = 0
	for s in series:
		if (a[s[1]-1] - a[s[0]-1]) == s[2]:
			score += s[3]

	if score > max_score: max_score = score

print(max_score)

Solution (Python):
import itertools
N, M, Q = list(map(int, input().split()))
a = []
b = []
c = []
d = []

for i in range(Q):
  aa, bb, cc, dd = list(map(int, input().split()))
  a.append(aa)
  b.append(bb)
  c.append(cc)
  d.append(dd)

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


res = 0
for s in itertools.combinations_with_replacement(Ms, N):
  sum_ = 0
  for j in range(Q):
    if s[b[j]-1] - s[a[j]-1] == c[j]:
      sum_ += d[j]
  if sum_ > res:
    res = sum_

print(res)

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


def check(arr):
    num = 0
    for e in A:
        if arr[e[1]-1] - arr[e[0]-1] == e[2]:
            num += e[3]

    
    return num


def dfs(idx):
    
    if idx == -1:
        res = check(B)
        max_res[0] = max(max_res[0], res)

    else:
        prev = B[idx+1] if idx != n-1 else m
        for j in range(1, prev+1):
            B[idx] = j
            dfs(idx-1)

B = [0]*n
max_res = [0]
dfs(n-1)

print(max_res[0])

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

def C():
    N, M, Q = map(int, input().split())
    ans = 0
    possibles = []
    def generate(cur_list, last):
        if len(cur_list) == N:
            possibles.append(cur_list)
            return
        for j in range(last, M+1):
            generate(cur_list+[j], j)

    generate([], 1)

    D = [0 for i in range(len(possibles))]

    
    for i in range(Q):
        a, b, c, d = map(int, input().split())
        for i, p in enumerate(possibles):
            if p[b-1] - p[a-1] == c:
                D[i] += d
    
    print(max(D))

C()

Solution (Python):
import itertools

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

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

li = []
mx = 0

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

for v in itertools.combinations_with_replacement(m_li,n):
    buf = 0
    for i in range(q):
        a = li[i][0]
        b = li[i][1]
        c = li[i][2]
        d = li[i][3]
        if v[b-1] - v[a-1] == c:
            buf += d
    if buf >= mx:
        mx = buf

print(mx)

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

import itertools
lists = list(itertools.combinations_with_replacement(range(1,M+1),N))

def check(ls):
    count = 0
    for i in range(Q):
        if ls[req[i][1] - 1] - ls[req[i][0] - 1] == req[i][2]:
            count += req[i][3]
    return count

for a in lists:
    s = check(a)
    if s > ans:
        ans = s

print(ans)

Solution (Python):
import itertools

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

l=[]
for v in itertools.combinations_with_replacement(list(range(1,m+1)), n):
    l.append(list(v))

for i in l:
    ans1=0
    for j in range(q):
        ans1+=lis[j][3]*((i[lis[j][1]-1]-i[lis[j][0]-1])==lis[j][2])
    ans=max(ans,ans1)
print(ans)

Solution (Python):
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N,M,Q = isRaw()
    abcds = [isRaw() for m in range(Q)]
    def dfs(As):
        if len(As)==N:
            cur = 0
            for abcd in abcds:
                a,b,c,d = abcd
                if As[b-1]-As[a-1] == c:
                    cur+=d
            return cur 
        tmp = 0
        for a in range(As[-1],M+1):
            tmp = max(dfs(As+[a]),tmp)
        return tmp
    return dfs([1])
    
if __name__ == "__main__":
    print(main())

Solution (Python):
import itertools

x = input().split(' ')
n = int(x[0])
m = int(x[1])
q = int(x[2])

abcd = []

for i in range(q):
  x = input().split(' ')
  tmp = []
  for j in range(4):
    tmp.append(int(x[j]))
    
  abcd.append(tmp)
  

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

score = 0

for candidate in a_candidates:
  score_tmp = 0
  for abcd_ in abcd:
    a = abcd_[0]-1
    b = abcd_[1]-1
    c = abcd_[2]
    d = abcd_[3]
    
    if (candidate[b]-candidate[a]) == c:
      score_tmp += d
      

  if score_tmp > score:
    score = score_tmp
    
print(score)

Solution (Python):
import itertools
n, m, q = [int(i) for i in input().split(" ")]
A = []
for i in range(q):
    A.append([int(i) for i in input().split(" ")])
given = [i for i in range(1, m + 1)]
ans = itertools.combinations_with_replacement(given, n)
answer = 0
for solve in ans:
    now = 0
    for i in range(q):
        if (solve[A[i][1] - 1] - solve[A[i][0] - 1]) == A[i][2]:
            now += A[i][3]
    if (now > answer):
        answer = 0 + now
print(answer)

Solution (Python):
n,m,q=map(int,input().split())
a=[0]*q
b=[0]*q
c=[0]*q
d=[0]*q
x=[0]*10
s=0
ans=0
for i in range(q):
  a[i],b[i],c[i],d[i]=map(int,input().split())
for a0 in range(1,m+1):
  x[0]=a0
  for a1 in range(x[0],m+1):
    x[1]=a1
    for a2 in range(x[1],m+1):
      x[2]=a2
      for a3 in range(x[2],m+1):
        x[3]=a3
        for a4 in range(x[3],m+1):
          x[4]=a4
          for a5 in range(x[4],m+1):
            x[5]=a5
            for a6 in range(x[5],m+1):
              x[6]=a6
              for a7 in range(x[6],m+1):
                x[7]=a7
                for a8 in range(x[7],m+1):
                  x[8]=a8
                  for a9 in range(x[8],m+1):
                    x[9]=a9
                    for j in range(q):
                      if x[b[j]-1]-x[a[j]-1]==c[j]:
                        s=s+d[j]
                    ans=max(ans,s)
                    s=0
print(ans)

Solution (Python):
from itertools import combinations
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(20000000)

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

























def dfs(A, depth, max_a):
    if depth == n:
        score = 0
        for a, b, c, d in abcd:
            if A[b] - A[a] == c:
                score += d
        return score
    ans = 0
    for i in range(max_a, m+1):
        ans = max(ans, dfs(A + [i], depth+1, i))
    return ans

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

Solution (Python):
import itertools

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

if __name__ == '__main__':
  main()

Solution (Python):

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

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

def next(A):
  index = -1
  while True:
    if A[index]<M:
      return A[:index]+[A[index]+1 for i in range(-index)]
    else:
      index -= 1
      if index == -N:
        return [-1]

def calc_score(A):
  score = 0
  for q in list_query:
    if A[q[1]-1]-A[q[0]-1]==q[2]:
      score += q[3]
  return score

max_score = 0
A = [1 for i in range(N)]

while A[0]!=-1:
  max_score = max(max_score, calc_score(A))
  A = next(A)

print(max_score)

Solution (Python):
from itertools import combinations_with_replacement as comb

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

ls_q = [tuple(map(int, input().split())) for q in range(Q)]

def calc(c):
    result = 0
    for q in ls_q:
        if c[q[1] - 1] - c[q[0] - 1] == q[2]:
            result += q[3]
            
    return result

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

c = comb(ls, N)
max_result = 0
while True:
    try:
        max_result = max(calc(next(c)), max_result)
    except StopIteration:
        break

print(max_result)

Solution (Python):
n,m,q = map(int,input().split())
sum_=0

import itertools
 
A_kouho = []
for i in itertools.combinations_with_replacement(range(1, m+1), n):
    i = (1,) + i + (m,)
    A_kouho.append(i)


four_r = []
for j in range(q):
  Q = list(map(int, input().split()))
  four_r.append(Q)


max_ = 0
for A in A_kouho:
  sum_ = 0
  for j in four_r:
    
    if A[j[1]]-A[j[0]]==j[2]:
      sum_+=j[3]
    if sum_>max_: max_=sum_
print(max_)

Solution (Python):
N, M, Q = [int(s) for s in input().split()]
dat = [[int(s) for s in input().split()] for _ in range(Q)]
A = [0] * N
result = []


def Calc(count):
    global result
    global A
    cnt = 0
    if count == N:
        for d in dat:
            if A[d[1] - 1] - A[d[0] - 1] == d[2]:
                cnt += d[3]
        return cnt
    else:
        max_val = 0
        if count == 0:
            start = 1
        else:
            start = A[count-1]

        for i in range(start, M + 1):
            A[count] = i
            max_val = max(max_val, Calc(count + 1))
        return max_val


print(Calc(0))

Solution (Python):
import itertools

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

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

rr = range(1, M + 1)
it = itertools.combinations_with_replacement(rr, N)

M_ans = 0

for A in it:
    ans = 0
    for a, b, c, d in ABCD:
        if A[b - 1] - A[a - 1] == c:
            ans += d

    if ans > M_ans:
        M_ans = ans

print(M_ans)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *
































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,M,Q = inputMap()
	A = []
	for i in range(Q):
		a,b,c,d = inputMap()
		A.append((a,b,c,d))

	retu = []
	for i1 in range(M,0,-1):
		tmp = []
		for i2 in range(M,0,-1):
			if i1 > i2:
				break
			for i3 in range(M,0,-1):
				if i2 > i3:
					break
				for i4 in range(M,0,-1):
					if i3 > i4:
						break
					for i5 in range(M,0,-1):
						if i4 > i5:
							break
						for i6 in range(M,0,-1):
							if i5 > i6:
								break
							for i7 in range(M,0,-1):
								if i6 > i7:
									break
								for i8 in range(M,0,-1):
									if i7 > i8:
										break
									for i9 in range(M,0,-1):
										if i8 > i9:
											break
										for i10 in range(M,0,-1):
											if i9 > i10:
												break
											tmp.append(i1)
											tmp.append(i2)
											tmp.append(i3)
											tmp.append(i4)
											tmp.append(i5)
											tmp.append(i6)
											tmp.append(i7)
											tmp.append(i8)
											tmp.append(i9)
											tmp.append(i10)
											retu.append(tmp[:N])
											tmp = []
	ans = 0
	for i in retu:
		
		score = 0
		for vol in A:
			a,b,c,d = vol
			
			if int(i[b-1]) - int(i[a-1]) == c:
				score += d

		if score > ans:
			ans = score

	print(ans)






def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Solution (Python):
import itertools
n, m, q = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(q)]
ml = list(range(1, m+1))
a_list = list(itertools.combinations_with_replacement(ml,n))
ans_l = []
for l in a_list:
    tmp = 0
    for a, b, c, d in li:
        if l[b-1] - l[a-1] == c:
            tmp += d
    ans_l.append(tmp)
print(max(ans_l))

Solution (Python):
import itertools

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

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

ans = 0
for i in range(len(list_ex)):
    list_ex2 = list_ex[i]
    ans2 = 0
    for j in range(q):
        listi2 = listi[j]
        ai = listi2[0]-1
        bi = listi2[1]-1
        ci = listi2[2]
        if (list_ex2[bi] - list_ex2[ai] == ci):
            ans2 += listi2[3]
    if (ans < ans2):
        ans = ans2

print(ans)

Solution (Python):
import itertools
N,M,Q = map(int,input().split())
n_list = list()
l = list()
d = list()
d_sum = list()
for i in range(1,M+1):
    l.append(i)
A_list = list(itertools.combinations_with_replacement(l,N))
for i in range(Q):
    n_list.append(list(map(int,input().split())))
for A in A_list:
    for i in range(Q):
        if A[n_list[i][1]-1]-A[n_list[i][0]-1] == n_list[i][2]:
            d.append(n_list[i][3])
        else:
            d.append(0)
    d_sum.append(sum(d))
    d.clear()
print(max(d_sum))

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush

from decimal import *
































def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007




def main():
	N,M,Q = inputMap()
	A = []
	for i in range(Q):
		a,b,c,d = inputMap()
		A.append((a,b,c,d))

	retu = []
	for i1 in range(M,0,-1):
		tmp = []
		for i2 in range(M,0,-1):
			if i1 > i2:
				break
			for i3 in range(M,0,-1):
				if i2 > i3:
					break
				for i4 in range(M,0,-1):
					if i3 > i4:
						break
					for i5 in range(M,0,-1):
						if i4 > i5:
							break
						for i6 in range(M,0,-1):
							if i5 > i6:
								break
							for i7 in range(M,0,-1):
								if i6 > i7:
									break
								for i8 in range(M,0,-1):
									if i7 > i8:
										break
									for i9 in range(M,0,-1):
										if i8 > i9:
											break
										for i10 in range(M,0,-1):
											if i9 > i10:
												break
											tmp.append(i1)
											tmp.append(i2)
											tmp.append(i3)
											tmp.append(i4)
											tmp.append(i5)
											tmp.append(i6)
											tmp.append(i7)
											tmp.append(i8)
											tmp.append(i9)
											tmp.append(i10)
											retu.append(tmp[:N])
											tmp = []
	ans = 0
	for i in retu:
		
		score = 0
		for vol in A:
			a,b,c,d = vol
			
			if int(i[b-1]) - int(i[a-1]) == c:
				score += d

		if score > ans:
			ans = score

	print(ans)






def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y



def H(n, r, mod=10**9+7):
	
	
    return combination(n+r-1, r, mod)


class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        
        
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv



def dfs(graph,parent,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

if __name__ == "__main__":
	main()

Solution (Python):

import itertools
def main():

    
    
    s = [int(x) for x in input().split(' ')]
    n = s[0]
    m = s[1]
    q = s[2]
    t_list = []
    for i in range(q):
        s = [int(x) for x in input().split(' ')]
        t_list.append(s)

    seq = [x for x in range(1, m+1)]
    candidate_list = list(itertools.combinations_with_replacement(seq, n))

    candidate_d_list = []
    candidate_d_list.append(0)
    for candidate in candidate_list:
        d_list = []
        d_list.append(0)

        for t in t_list:
            a = t[0]
            b = t[1]
            c = t[2]
            d = t[3]
            
            if candidate[b-1] - candidate[a-1] == c:
                d_list.append(d)
        candidate_d_list.append(sum(d_list))

    
    print(max(candidate_d_list))


if __name__ == '__main__':
    main()

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

ans=[1 for i in range(n)]
nans=0

while ans!=[m for i in range(n)]:
    
    sum=0
    for i in range(q):
        if ans[a[i][1]-1]-ans[a[i][0]-1]==a[i][2]:
            sum+=a[i][3]
    
    nans=max(nans,sum)
    ans[-1]+=1
    while max(ans)>m:
        max_ind=ans.index(m+1)
        ans[max_ind-1]+=1
        ue=ans[max_ind-1]
        for i in range(max_ind,len(ans)):
            ans[i]=ue
sum=0
for i in range(q):
    if ans[a[i][1]-1]-ans[a[i][0]-1]==a[i][2]:
        sum+=a[i][3]
nans=max(nans,sum)

print(nans)

Solution (Python):
n, m, q =  list(map(int, input().split()))
aa = []
bb =[]
cc = []
dd =[]
for i in range(q):
    a,b,c,d =  list(map(int, input().split()))
    aa.append(a)
    bb.append(b)
    cc.append(c)
    dd.append(d)

def ev(A):
    s = 0
    for i in range(q):
        if A[bb[i] - 1] - A[aa[i] - 1] == cc[i]:
            s += dd[i]
    return s

A = [0] * n
s = ev(A)
for i0 in range(m):
    for i1 in range(i0, m):
        for i2 in range(i1, m):
            for i3 in range(i2, m):
                for i4 in range(i3, m):
                    for i5 in range(i4, m):
                        for i6 in range(i5, m):
                            for i7 in range(i6, m):
                                for i8 in range(i7, m):
                                    for i9 in range(i8, m):
                                        A = [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9][:n]
                                        s = max([s, ev(A)])
print(s)

Solution (Python):
from itertools import combinations_with_replacement


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

points = []
for A in combinations_with_replacement(range(1, m + 1), n):
    
    point = 0
    for a, b, c, d in Q:
        if A[b-1] - A[a-1] == c:
            point += d
    points.append(point)

print(max(points))

Solution (Python):
N, M, Q = map(int, input().split())
abcd = []
for i in range(Q): abcd.append(list(map(int, input().split())))
ans = 0
per_lst = []
def make_per(lst, n, m):
    n_lst = lst.copy()
    n_lst.append(0)
    if n == 1:
        for i in range(1, m+1):
            n_lst = n_lst.copy()
            n_lst[-1] = i
            if len(n_lst) > 1:
                if i >= n_lst[-2]:
                    per_lst.append(n_lst)
            else:
                per_lst.append(n_lst)
    else:
        for i in range(1, m+1):
            n_lst[-1] = i
            if len(n_lst) > 1:
                if i >= n_lst[-2]:
                    make_per(n_lst, n-1, m)
            else:
                make_per(n_lst, n-1, m)

make_per([], N, M)


maxi = 0
for per in per_lst:
    score = 0
    for i in range(Q):
        a, b, c, d = abcd[i][0], abcd[i][1], abcd[i][2], abcd[i][3]
        a -= 1
        b -= 1
        if (per[b] - per[a]) == c: score += d
    if score > maxi: maxi = score
print(maxi)

Solution (Python):
n, m, q = [int(v) for v in input().split()]
a = []
b = []
c = []
d = []
for i in range(q):
    line = [int(v) for v in input().split()]
    a.append(line[0])
    b.append(line[1])
    c.append(line[2])
    d.append(line[3])

ans = 0

def calc(nums):
    ret = 0
    for i in range(q):
        if nums[b[i]-1] - nums[a[i]-1] == c[i]:
            ret += d[i]
    return ret

def solve(n, m, buf):
    if n == 0:
        global ans
        ans = max(ans, calc(buf))
        return

    if buf:
        for i in range(buf[-1], m+1):
            new_buf = buf[:]
            new_buf.append(i)
            solve(n-1, m, new_buf)
    else:
        for i in range(1, m+1):
            new_buf = buf[:]
            new_buf.append(i)
            solve(n-1, m, new_buf)

solve(n, m, [])
print(ans)

Solution (Python):
n,m,q=[int(i) for i in input().split()]
abcd=[]

import itertools

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


for i in range(q):
    abcd.append([int(i) for i in input().split()])
ans=0

for listA in A:
    count=0
    for kumi in abcd:
        a,b,c,d=kumi
        
        if listA[b-1]-listA[a-1]==c:
            count+=d
    ans=max(ans,count)
print(ans)

Solution (Python):
n,m,q = map(int, raw_input().split(' '))
reqs= [map(int, raw_input().split(' ')) for _ in range(q)]
max_ = [0]

def dfs(i, cur, n, m, reqs ):
	if n == 0:
		score = 0
		for a,b,c,d in reqs:
			if cur[b-1] - cur[a-1] == c: score += d
		max_[0] = max(max_[0], score)
		return 

	for j in range(i, m+1):
		dfs(j, cur + [j], n-1, m, reqs)

dfs(1, [], n, m, reqs)
print max_[0]

Solution (Python):
from sys import stdin,stdout
input=stdin.buffer.readline

ip=[int(x) for x in input().split()]
n=ip[0]
m=ip[1]
q=ip[2]

ai=[]
bi=[]
ci=[]
di=[]
for i in range(q):
	ip=[int(x) for x in input().split()]
	ai.append(ip[0])
	bi.append(ip[1])
	ci.append(ip[2])
	di.append(ip[3])

a=[]
if n==10:
	for i1 in range(1,m+1):
		for i2 in range(i1,m+1):
			for i3 in range(i2,m+1):
				for i4 in range(i3,m+1):
					for i5 in range(i4,m+1):
						for i6 in range(i5,m+1):
							for i7 in range(i6,m+1):
								for i8 in range(i7,m+1):
									for i9 in range(i8,m+1):
										for i10 in range(i9,m+1):
											a.append([i1,i2,i3,i4,i5,i6,i7,i8,i9,i10])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==9:
	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):
										a.append([i1,i2,i3,i4,i5,i6,i7,i8,i9])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==8:
	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):
									a.append([i1,i2,i3,i4,i5,i6,i7,i8])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==7:
	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):
								a.append([i1,i2,i3,i4,i5,i6,i7])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==6:
	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):
							a.append([i1,i2,i3,i4,i5,i6])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==5:
	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):
						a.append([i1,i2,i3,i4,i5])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==4:
	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):
					a.append([i1,i2,i3,i4])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==3:
	for i1 in range(1,m+1):
		for i2 in range(i1,m+1):
			for i3 in range(i2,m+1):
				a.append([i1,i2,i3])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)
elif n==2:
	for i1 in range(1,m+1):
		for i2 in range(i1,m+1):
			a.append([i1,i2])

	ans=0
	for i in range(len(a)):
		m=0
		for j in range(q):
			if a[i][bi[j]-1]-a[i][ai[j]-1]==ci[j]:
				m+=di[j]
		if ans<m:
			ans=m

	print(ans)