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
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):
from itertools import combinations_with_replacement


def main():
    n,m,q = map(int,input().split())
    num_lst = []
    for i in range(q):
        num_lst.append(list(map(int,input().split())))
    l = list(range(1,m+1))
    A = list(combinations_with_replacement(l,n))

    mx = 0
    for now_A in A:
        score = 0
        for nums in num_lst:
            a,b,c,d = nums
            if now_A[b-1] - now_A[a-1] == c:
                score += d
        mx = max(mx,score)
    print(mx)



if __name__ == '__main__':
    main()

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

def score(List):
    res = 0
    for a, b, c, d in ques:
        if List[b] - List[a] == c:
            res += d

    return res


def dfs(i, x):
    res = 0
    if i == n:
        return score(x)

    for j in range(max(x[-1], 1), m+1):
        res = max(res, dfs(i+1, x+[j]))

    return res

print(dfs(0, [0]))

Solution (Python):
import itertools

N,M,Q = map(int,input().split())
abcd = [list(map(int,input().split())) for i in range(Q)]
nums = []
maxp = 0

for i in range(M):
    nums.append(i+1)

for retsu in itertools.combinations_with_replacement(nums, N):
    p = 0
    for i in range(Q):
        a = abcd[i][0]-1
        b = abcd[i][1]-1
        c = abcd[i][2]
        d = abcd[i][3]
        if retsu[b]-retsu[a] == c:
            p += d
    maxp = max(p,maxp)
    
print(maxp)

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

num = 0
nax = 0

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

for com in list(itertools.combinations_with_replacement(nums, n)):
    num = 0
    for j in range(q):
        if com[l[j][1]-1]-com[l[j][0]-1] == l[j][2]:
            num += l[j][3]
    nax = max(num, nax)
print(nax)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

import itertools

n,m,q=MAP()

a=[list(MAP()) for i in range(q)]

ans=0
for ls in list(itertools.combinations_with_replacement(range(1,m+1), n)):
    res=0
    for i in range(len(a)):
        if ls[a[i][1]-1]-ls[a[i][0]-1]==a[i][2]:
            res+=a[i][3]
    if ans<=res:
        ans=res
print(ans)

Solution (Python):
import itertools


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

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

for seq in seqs:
    point = 0
    for query in queries:
        a, b, c, d = query
        if seq[b-1] - seq[a-1] == c:
            point += d
    if point > ans:
        ans = point

print(ans)

Solution (Python):
n,m,q=map(int,input().split())
arr=[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):
                    tmp=0
                    arrs=[0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                    for a,b,c,d in arr:
                      if arrs[b]-arrs[a]==c:
                        tmp+=d
                    ans=max(ans,tmp)
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,q = inpl()
abc = [inpl() for _ in range(q)]
q = deque()
q.append([1])
res = 0

while q:
    now = q.popleft()
    if len(now) == n:
        ans = 0
        for i,x in enumerate(abc):
            a,b,c,d = x
            b -= 1; a -= 1
            if now[b] - now[a] == c:
                ans += d
        res = max(ans, res)
        continue
    for i in range(now[-1], m+1):
        q.append(now + [i])
print(res)

Solution (Python):
n, m, q = map(int, input().split())
a, b, c, d = [[0]*q for i in range(4)]
for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1

def dfs(vec, mx, cnt):
    if cnt:
        tmp = 0
        for i in range(mx, m+1):
           tmp = max(tmp, dfs(vec+[i], i, cnt-1))
        return tmp
    else:
        tmp = 0
        for i in range(q):
            if vec[b[i]]-vec[a[i]]==c[i]: tmp += d[i]
        return tmp
print(dfs([], 1, n))

Solution (Python):
if __name__ == '__main__':
    from sys import stdin
    
    
    input = stdin.readline

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

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

    
    ans = 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):
                                        for j in range(i,m+1):
                                            num = [a, b, c, d, e, f, g, h, i, j]
                                            num_sum = 0
                                            for k, l, o, p in abcd:
                                                if num[l]-num[k] == o:
                                                    num_sum += p
                                            
                                            if num_sum > ans:
                                                ans = num_sum
    print(ans)

Solution (Python):
N,M,Q = [int(v) for v in input().split()]

querys = [[int(v) for v in input().split()] for _ in range(Q)]

ans = 0
L = []

def dfs(now,last = 1):
    if len(now) == N:
        L.append(now)
        return

    for i in range(1,M+1):
        if i >= last:
            c = now[:]
            c.append(i)
            dfs(c,last=i)

dfs([1])

for l in L:
    tmp = 0
    for q in querys:
        a,b,c,d = q
        if l[b-1] - l[a-1] == c: tmp+= d
    ans = max(ans,tmp)
print(ans)

Solution (Python):
from math import gcd
from itertools import combinations_with_replacement

def readlines(n):
    for _ in range(n):
        a, b, c, d = map(int, input().split())
        yield a-1, b-1, c, d

def main():
    n, m, q = map(int, input().split())
    X = list(readlines(q))

    for comb in combinations_with_replacement(range(1, m+1), n):
        x = 0
        for a, b, c, d in X:
            if comb[b] - comb[a] == c:
                x += d
        yield x

print(max(main()))

Solution (Python):

import sys


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

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

    max_p = [0]

    def ser (l, prev, dep):
        if dep == N:
            
            return cal_p(l)
        else:
            for i in range(prev, M+1):
                max_p[0] = max(ser(l + [i], i, dep+1), max_p[0])
            return 0
    
    max_p = max(ser([],1,0), max_p[0])
    print(max_p)

    return



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

if __name__ == '__main__':
    main()

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

l_list = list(itertools.combinations_with_replacement(l,n))


ans = 0

for i in range(len(l_list)):
    b = 0
    for j in range(q):
        if (l_list[i][a[j][1]-1] - l_list[i][a[j][0]-1] == a[j][2]):
            b += a[j][3]
    
    if (ans < b):
        ans = b
print(ans)

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

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

best_score = 0
for A in A_cand:
    d_sum = 0
    for i in range(Q):
        a = abcd[i][0] - 1
        b = abcd[i][1] - 1
        c = abcd[i][2]
        d = abcd[i][3]
        if A[b] - A[a] == c:
            d_sum += d
    if best_score < d_sum:
        best_score = d_sum

print(best_score)

Solution (Python):
def dfs(x, y):
    if len(x) == n:
        l.append(x)
        return
    else:
        for i in range(y, m+1):
            z = list(x)
            z.append(i)
            dfs(z, i)
        return

n, m, q = map(int, input().split())
ans = 0
l = []
dfs([], 1)
A = []
B = []
C = []
D = []
for _ 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)
for i in range(len(l)):
    cnt = 0
    for j in range(q):
        if l[i][B[j]]-l[i][A[j]] == C[j]:
            cnt += D[j]
    ans = max(cnt, ans)
print(ans)

Solution (Python):
import itertools
n,m,q = map(int,input().split())
A = []
for i in range(q):
    A.append(list(map(int,input().split())))
cand = [i for i in range(1,m+1)]
ans = 0
for v in itertools.combinations_with_replacement(cand,n):
    total = 0
    for j in range(q):
        
        if (v[A[j][1]-1] - v[A[j][0]-1]) == A[j][2]:
            total += A[j][3]
    ans = max(ans,total)
print(ans)

Solution (Python):
import itertools
N,M,Q = map(int,input().split())
X = []
for _ in range(Q):
    a,b,c,d = map(int,input().split())
    X.append([a,b,c,d])
Y = [i for i in range(1,M+1)]
Z = list(itertools.combinations_with_replacement(Y,N))

ans = 0
for z in Z:
    
    tmp = 0
    for x in X:
        
        if z[x[1]-1] - z[x[0]-1] == x[2]:
            tmp += x[3]
    
    if tmp > ans:
        ans = tmp
print(ans)

Solution (Python):
from sys import stdin
from itertools import combinations_with_replacement

def input():
    return stdin.readline().strip()


def main():
    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

    ans = 0
    for seq in combinations_with_replacement(range(1, M + 1), N):
        score = 0
        for i in range(Q):
            if seq[b[i]] - seq[a[i]] == c[i]:
                score += d[i]

        ans = max(ans, score)

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import itertools


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

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

ans = 0
for A in itertools.combinations_with_replacement(all, N):
    point = 0
    for i in range(Q):
        ai, bi, ci, di = abcd[i]
        if A[bi - 1] - A[ai - 1] == ci:
            point += di
    ans = max(point, ans)

print(ans)

Solution (Python):
import itertools as it
import numpy as np

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

arange =  np.arange(1,M+1)
As = list(it.combinations_with_replacement(arange,N))

m = 0
for A in As:
    tmp = 0
    for q in a:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            tmp += q[3]
    if m < tmp:
        m = tmp

print(m)

Solution (Python):


import sys
sys.setrecursionlimit(300000)
from itertools import combinations, combinations_with_replacement



def solve(n, m, Q, a, b, c, d, X):
    cans = list(combinations_with_replacement(range(1, m + 1), n))
    
    ret = 0
    for can in cans:
        tmp = 0
        for i in range(Q):
            if can[b[i] - 1] - can[a[i] - 1] == c[i]:
                tmp += d[i]
        ret = max(tmp, ret)
    print(ret)
    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)  
    X = []
    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))
        X.append((a[i], b[i], c[i], d[i]))
    solve(N, M, Q, a, b, c, d, X)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

input = sys.stdin.buffer.readline


import itertools

def cal(n, m, q, arr):

    def cal_set(s):

        score = 0
        s_arr = list(s)
        l = len(s_arr)

        for a, b, c, d, in arr:
            if 0 <= a - 1 < l and 0 <= b - 1 < l:
                if s_arr[b - 1] - s_arr[a - 1] == c:
                    score += d

        return score

    max_score = 0

    comb_list = itertools.combinations_with_replacement(list(range(m)), n)

    for s in comb_list:
        max_score = max(max_score, cal_set(s))

    return max_score


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

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

print (cal(n, m, q, arr))

Solution (Python):


def main():
    N, M, Q = [int(x) for x in input().split()]
    queries = [[int(x) for x in input().split()] for _ in range(Q)]

    ans = float("-inf")
    import itertools
    for A in itertools.combinations_with_replacement(range(1, M+1), N):
        
        s = 0
        for a, b, c, d in queries:
            if A[b-1] - A[a-1] == c:
                s += d
        ans = max(ans, s)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import itertools as itt
def resolve():
    N,M,Q = map(int,input().split())
    
    abcd = [list(map(int,input().split())) for i in range(Q)]
    mx = 0
    for A in itt.combinations_with_replacement(range(1,M+1),N):
        score =0

        for a,b,c,d in abcd:
            if A[b-1]-A[a-1]==c:
                score+=d
        mx = max(score,mx)
    print(mx)





if __name__ == "__main__":
    
    resolve()

Solution (Python):
from collections import deque






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

ans = 0
tmp = []

def dfs():
    global tmp
    stack = deque([[[], 0]])
    while stack:
        cur, i = stack.pop()
        if i == n:
            tmp.append(cur)
            continue
        mi = 1
        if i:
            mi = cur[-1]
        for next in range(mi, m+1):
            stack.append([cur+[next], i+1])
dfs()


for item in tmp:
    cand = 0
    for a, b, c, d in abcd:
        if item[b-1] - item[a-1] == c:
            cand += d
    ans = max(ans, cand)

print(ans)

Solution (Python):
N,M,Q = map(int,input().split())
L = list(range(1,M+1))
X = list()
for i in range(Q):
  X.append(list(map(int,input().split())))
  
ans = 0

import itertools
for l in itertools.combinations_with_replacement(L, N):
  l = sorted(list(l))
  s = 0
  for a,b,c,d in X:
    if l[b-1]-l[a-1]==c:
      s += d
  if ans < s:
    ans = s

print(ans)

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

As = list(itertools.combinations_with_replacement(range(1, M+1), N))
ans = 0
for a in As:
    point = 0
    for q in query:
        if a[q[1]-1] - a[q[0]-1] == q[2]:
            
            point += q[3]
    ans = max(ans, point)
    



print(ans)

Solution (Python):


import itertools

def main():
     n, m, q = map(int, input().split())
     q_list = list()
     a_list = [i for i in range(1, m+1)]

     for i in range(q):
          q_list.append(list(map(int, input().split())))

     ans = 0

     for v in itertools.combinations_with_replacement(a_list, n):
          target = list(v)
          
          score = 0
          for i in range(len(q_list)):
               point = q_list[i]
               
               if target[point[1]-1] - target[point[0]-1] == point[2]:
                    score += point[3]
          
          if ans < score:
               ans = score
          
     print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N, M, Q = map(int, input().split())
ptn = []
for i in range(Q):
    a,b,c,d = map(int, input().split())
    ptn.append([a-1,b-1,c,d])
mx = 0
def calc(arr):
    if len(arr) == N:
        global mx
        tot = 0
        
        
        for i in range(Q):
            if arr[ptn[i][1]] - arr[ptn[i][0]] == ptn[i][2]:
                tot += ptn[i][3]
        mx = max(mx, tot)
        return
    for i in range(1,M+1):
        if i < arr[-1]: continue
        calc(arr+[i])
for i in range(1,M+1):
    calc([i])
print(mx)

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

queue = [((1,), 1)]
maxvalue = 0
while queue:
    xs, n = queue.pop()
    if n == N:
        t = 0
        for a, b, c, d in abcd:
            if xs[b] - xs[a] == c:
                t += d
        maxvalue = max(t, maxvalue)
        continue
    for i in range(xs[n - 1], M + 1):
        queue.append((xs + (i,), n + 1))
print(maxvalue)

Solution (Python):
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

n = len(A)
score = np.zeros(n, np.int32)
m = map(int, read().split())
for a, b, c, d in zip(m, m, m, m):
    cond = A[:, b - 1] - A[:, a - 1] == c
    score += d * cond

print(score.max())

Solution (Python):
from itertools import combinations_with_replacement
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

def check(n, m, l, a):
    if len(a) == n:
        point = 0
        for i in range(len(l)):
            if a[l[i][1]-1]-a[l[i][0]-1] == l[i][2]:
                point += l[i][3]
        return point
    point = 0
    if len(a) == 0:
        start = 1
    else:
        start = a[-1]
    for i in range(start, m+1):
        point = max(point, check(n, m, l, a+[i]))
    return point

print(check(n, m, l, []))

Solution (Python):
import itertools

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

A = list(range(1,m+1))

ptr = list(itertools.combinations_with_replacement(A, n))

ans = 0

for i in ptr:
    tmp = 0
    for a,b,c,d in abcd:
        if i[b-1] - i[a-1] == c:
            tmp += d
    ans = max(ans, tmp)

print(ans)

Solution (Python):
from itertools import combinations_with_replacement

def point(A):
    res = 0
    for i in range(Q):
        if x[i][1] > len(A):
            continue
        else:
            if A[x[i][1]-1] - A[x[i][0]-1] == x[i][2]:
                res += x[i][3]
    return res


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

ans = 0
for A in combinations_with_replacement(range(1, M+1), N):
    ans = max(ans, point(A))

print(ans)