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 itertools
def main():
    n, m, q = map(int, input().split())
    matrix = []
    for _ in range(q):
        row = list(map(int, input().split()))
        matrix.append(row)
    
    A = list(range(1, m+1))
    ans = 0
    for tmp_A in itertools.combinations_with_replacement(A, n):
        tmp_A = sorted(list(tmp_A))
        tmp_ans = 0
        for row in matrix:
            
            
            tmp = tmp_A[row[1] - 1] - tmp_A[row[0]- 1]
            if row[2] == tmp:
                tmp_ans += row[3]
        if tmp_ans >= ans:
            ans = tmp_ans
            
    print(ans)
    
main()

Solution (Python):

N, M, Q = [int(i) for i in input().split()]
B = [[0, 0, 0, 0] for i in range(Q)]
for i in range(Q):
    B[i][0], B[i][1], B[i][2], B[i][3] = [int(j) for j in input().split()]
MAXC = [0]

def dfs(A, pre):
    
    if len(A) == N:
        counter = 0
        for i in range(Q):
            if A[B[i][1]-1] - A[B[i][0]-1] == B[i][2]:
                counter += B[i][3]
        if MAXC[0] < counter:
            MAXC[0] = counter
        return 
    for v in range(pre, M+1):
        A.append(v)
        dfs(A, v)
        A.pop() 
dfs([], 1)
print(MAXC[0])

Solution (Python):



def dfs(seq):
    ans = 0
    if len(seq) == N:
        score_ret = 0
        for a, b, c, d in data:
            if seq[b-1] - seq[a-1] == c:
                score_ret += d
        return score_ret
    else:
        for i in range(seq[-1], M+1):
            seq_next = seq + (i,)
            score = dfs(seq_next)
            ans = max(ans, score)
    
    return ans


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

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

ans = -1
score = dfs((1,))
ans = max(ans, score)
print(ans)

Solution (Python):



from collections import deque

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


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

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

ans = -1

que = deque()

for i in range(1, M+1):
    que.append([i])


while que:
    seq = que.popleft()

    if len(seq) == N:
        score = calc(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], M+1):
            seq_next = seq + [i]
            que.append(seq_next)

print(ans)

Solution (Python):



from itertools import combinations_with_replacement as comb_rplc


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

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

ans = -1

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

print(ans)

Solution (Python):
n,m,q=map(int,input().split())
e=[list(map(int,input().split())) for _ in range(q)]
ans=0
for i in range(1<<(m+n)):
  a=[1]
  for j in range(m+n):
    if (i>>j)&1:a[-1]+=1
    else:a+=[a[-1]]
    if a[-1]>m:
      flag=0
      break
    if len(a)>n:
      flag=1
      break
  else:flag=1
  if flag==0 or len(a)<n:continue
  cnt=0
  for s,t,u,v in e:
    if a[t-1]-a[s-1]==u:cnt+=v
  ans=max(ans,cnt)
print(ans)

Solution (Python):
def dfs(seq):
    ans = 0

    if len(seq) == n:
        score = 0
        for a, b, c, d in req:
            if seq[b-1] - seq[a-1] == c:
                score += d
        return score
    else:
        for i in range(seq[-1], m+1):
            next_seq = seq + (i,)
            score = dfs(next_seq)
            ans = max(ans, score)
    return ans

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

print(dfs((1,)))

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

def func(a):
    if a[-1] != m: 
        a[-1] += 1 
        return a
    else: 
        d = n - 1
        while d > 0 and a[d] == m:
            d = d - 1 
        if d < 0:
            return a
        else: 
            a[d] += 1
            for x in range(d,n): 
                a[x] = a[d]
            return a
            
ans = 0
a[-1] = 0
while sum(a) != n*m:
    func(a)
    di = 0
    for i in range(q): 
        if a[abcd[i][1]-1] - a[abcd[i][0]-1] == abcd[i][2]: 
            di += abcd[i][3] 
    ans = max(ans, di) 
print(ans)

Solution (Python):
from _collections import deque

def cacl(seq):
    score = 0
    for a, b, c, d in req:
        if seq[b-1] - seq[a-1] == c:
            score += d
    return score

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

ans = 0
que = deque()

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

while que:
    seq = que.popleft()

    if len(seq) == n:
        score = cacl(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], m + 1):
            seq_next = seq + [i]
            que.append(seq_next)
print(ans)

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

ans = 0

for seq in comb_rplc(range(1,m+1),n):
    now = 0
    for a, b, c, d in req:
        if seq[b-1] - seq[a-1] == c:
            now += d
    ans = max(ans, now)

print(ans)

Solution (Python):
n,m,q=map(int,input().split())
query=[]
for _ in range(q): query.append(list(map(int,input().split())))
ans=0
def rec(a):
    if len(a)==n+1:
        temp=0
        for qu in query:
            if a[qu[1]]-a[qu[0]]==qu[2]: temp+=qu[3]
        global ans
        ans=max(ans,temp)
        return
    for i in range(a[-1],m+1):
        cp=a[:]
        cp.append(i)
        rec(cp)
rec([1])
print(ans)

Solution (Python):
def main():
    import itertools
    n,m,q = map(int,input().split())
    Q = []
    for i in range(q):
        Q.append(list(map(int,input().split())))
    cmb = [i for i in range(1,m+1)]
    ans = 0
    for que in itertools.combinations_with_replacement(cmb,n):
        m = 0
        for i in range(q):
            [a,b,c,d] = Q[i]
            if que[b-1]-que[a-1]==c:
                m += d
        if m>ans:
            ans = m
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

n,m,q = lr()
abcd = [lr() for i in range(q)]
def getAns(s, num, l):
    if l == n:
        ret = 0
        for a,b,c,d in abcd:
            a-=1
            b-=1
            if s[b]-s[a] == c:
                ret+=d
        return ret
    else:
        ret = 0
        for i in range(num, m+1):
            tmp = s.copy()
            tmp.append(i)
            ret = max(ret, getAns(tmp, i, l+1))
        return ret
print(getAns([], 1, 0))

Solution (Python):
n, m, q = list(map(int, input().split()))
from collections import deque
ans = 0
def calc(seq):
    score = 0
    for a, b, c, d in req:
        if seq[b-1] - seq[a-1] == c:
            score+= d
    return score
req = [list(map(int, input().split())) for i in range(q)]

que = deque()

for h in range(1, m+1):
    que.append([h])

while que:
    seq = que.popleft()
    if len(seq) == n:
        score = calc(seq)
        ans = max(ans, score)
    else:
        for i in range(seq[-1], m+1):
            seq_next = seq + [i]
            que.append(seq_next)

print(ans)

Solution (Python):
L=[]
def make_list(n,m,p,l):
  if n==0:
    L.append(l)
  else:
    for i in range(p,m+1):
      make_list(n-1,m,i,l+[i])
  
N,M,Q = map(int,input().split())
T=[tuple(map(int,input().split())) for _ in range(Q)]
ans=0
make_list(N,M,1,[])
for l in L:
  tmp=0
  for a,b,c,d in T:
    if l[b-1]-l[a-1]==c:
      tmp+=d
  ans=max(ans,tmp)
print(ans)

Solution (Python):
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))

from itertools import combinations_with_replacement

ans = 0

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

print(ans)

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

Nums = [ i for i in range(M) ]
ans = -1
for v in combinations_with_replacement(Nums, N):
    cnt = 0
    for que in Ques:
        if v[que[1]-1]-v[que[0]-1] == que[2]: cnt += que[3]
    ans = max(ans, cnt)
print(ans)

Solution (Python):
length, Max, q = map(int,input().split())
query = [[0]*4 for _ in range(q)]
for i in range(q):
    a,b,c,d = map(int,input().split())
    query[i] = [a-1,b-1,c,d]
ans = 0
def dfs(A):
    if len(A) == length:
        global ans
        score = 0
        for i in range(q):
            a,b,c,d = query[i]
            if A[b] - A[a] == c:
                score += d
        ans = max(ans, score)
        return
    last = A[-1]
    for i in range(last,Max+1):
        A.append(i)
        dfs(A)
        A.pop()
dfs([1])
print(ans)

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

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

a = [1]*n
def next_a(a):
    if a[-1] != m:
        a[-1] += 1
    else:
        d = n-1
        while d > 0 and a[d] == m:
            d-=1
        if d < 0:
            return a
        a[d] += 1
        next = a[d]
        for i in range(d,n):
            a[i] = next
max = -1
a[-1] = 0
while sum(a) != n*m:
    next_a(a)
    test = 0
    for i in range(q):
        if a[abcd_list[i][1]-1] - a[abcd_list[i][0]-1] == abcd_list[i][2]:
            test += abcd_list[i][3] 
    if test > max:
        max = test

print(max)

Solution (Python):
from itertools import combinations_with_replacement

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

A_lst = combinations_with_replacement(range(1, M+1), N)
A_lst = list(map(list, A_lst))
A_lst.sort()

dm = 0 
for A in A_lst:
    ds = 0 
    for a, b, c, d in lst:
        if A[b-1] - A[a-1] == c:
            ds += d
    if ds > dm:
        dm = ds
print(dm)

Solution (Python):
n, m, q = list(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):
    score =0
    for ai, bi, ci, di in zip(a,b,c,d):
        if A[bi] - A[ai] == ci:
            score += di
    return score

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

print(dfs([]))

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):
    score = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if A[bi] - A[ai] == ci:
            score += di
    return score

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):
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):
    score = 0
    for ai, bi, ci, di in zip(a, b, c, d):
        if A[bi] - A[ai] == ci:
            score += di
    return score

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


def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return

    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)


ans, tempAns = 0, 0
for tempA in combinations_with_replacement(range(1, m + 1), n):
    tempAns = 0
    for a in A:
        if tempA[a[1] - 1] - tempA[a[0] - 1] == a[2]:
            tempAns += a[3]
    ans = max(ans, tempAns)
print(ans)

Solution (Python):
from itertools import *
N,M,Q = map(int,input().split())
abcd = [list(map(int,input().split())) for q in range(Q)]
print(max(sum(d for a,b,c,d in abcd if i[b-1]-i[a-1]==c) for i in combinations_with_replacement(range(M),N)))

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

n, m, q = [int(i) for i in input().strip().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append([int(i) for i in input().strip().split()])


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], n)

for A in canditates:
    _temp = 0
    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
sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline

n, m, q = [int(i) for i in input().strip().split()]
abcd = []
canditates = []
ans = 0


for _ in range(q):
    abcd.append([int(i) for i in input().strip().split()])


def helper(_min, _max, cur, res):
    if res == 0:
        canditates.append(list(cur))
    else:
        for i in range(_min, _max):
            cur.append(i)
            helper(i, _max, cur, res - 1)
            cur.pop()


helper(1, m + 1, [], n)

for A in canditates:
    _temp = 0
    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):
n, m, q = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(q)]

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

def dfs(pre, _min):
    if len(pre) == n:
        return score(pre)
    ret = 0
    for i in range(_min, m+1):
        new = pre + [i]
        ret = max(ret, dfs(new, i))
    return ret

print(dfs([], 1))

Solution (Python):
n, m, q = map(int, input().split())
a = [0]*q
b = [0]*q
c = [0]*q
d = [0]*q

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

ans = 0
while A[0] <= m:
    tmp = 0
    for i in range(q):
        if (A[b[i]-1] - A[a[i]-1]) == c[i]:
            tmp += d[i]
    if tmp > ans:
        ans = tmp
    
    A[-1] +=1
    for i in range(n-1,0,-1):
        if A[i] == m+1:
            A[i-1] +=1
            for j in range(len(A[i:])):
                A[i+j] = A[i-1]
print(ans)

Solution (Python):
from itertools import combinations_with_replacement

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

L = [i+1 for i in range(m)]
li = [input().split() for i in range(q)]

for i in range(q):
    li[i] = [int(x) for x in li[i]]

ans = 0
for v in combinations_with_replacement(L,n):
    sum1 = 0
    for i in li:
        if v[i[1]-1] - v[i[0]-1] == i[2]:
            sum1 +=i[3]
    ans = max(ans,sum1)
print(ans)

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

ans = 0
A = []


def dfs():
    global A, ans
    if len(A) == N:
        res = sum(t[3] for t in L if A[t[1]-1] - A[t[0]-1] == t[2])
        ans = max(ans, res)
    else:
        for a in range(A[-1] if A else 1, M + 1):
            A.append(a)
            dfs()
            A.pop()


dfs()
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):
                                        suuretsu = [i1, i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        tmp = 0
                                        for a,b,c,d in arr:
                                            if suuretsu[b-1] - suuretsu[a-1] == c:
                                                tmp += d
                                        ans = max(ans, tmp)
print(ans)

Solution (Python):
N, M, Q = map(int, input().split())
A, B, C, D = [],[],[],[]
for i in range(Q):
    a, b, c, d = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)

L = []
def dfs(S):
    if len(S) == N:
        L.append(S)
    elif S == "":
        for i in range(M):
            S = str(i)
            dfs(S)
    else:
        for i in range(int(S[-1]), M):
            dfs(S+str(i))
dfs("")

Ans = 0
for l in L:
    ans = 0
    for a, b, c, d in zip(A,B,C,D):
        if int(l[b-1]) - int(l[a-1]) == c:
            ans += d
    Ans = max(ans, Ans)
print(Ans)

Solution (Python):
from itertools import combinations_with_replacement

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

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

lst = list(combinations_with_replacement([i for i in range(1, M+1)], N))

ans = 0
for q in lst:
    ans_tmp = 0
    
    for i in range(Q):
        if(q[num[i][1]-1]-q[num[i][0]-1] == num[i][2]):
            ans_tmp += num[i][3]
    
    if(ans < ans_tmp):
        ans = ans_tmp
print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import combinations_with_replacement
def main():
    n, m, q = map(int, input().split())
    abcd = []
    for _ in range(q):
        q = tuple(map(int, input().split()))
        abcd.append(q)
    c1 = tuple(combinations_with_replacement(range(1,m+1), n))
    r = 0
    for ce in c1:
        t = 0
        for qe in abcd:
            a, b, c, d = qe
            a -= 1
            b -= 1
            if ce[b] - ce[a] == c:
                t += d
        r = max(r, t)
    print(r)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations_with_replacement

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

temp = list(combinations_with_replacement([i for i in range(1,m+1)],n))

ans = 0

for a_temp in temp:
    ans_temp = 0
    for i in range(q):
        if a_temp[a[i][1]-1] - a_temp[a[i][0]-1] == a[i][2]:
            ans_temp += a[i][3]
    if ans < ans_temp:
        ans = ans_temp
        
print(ans)

Solution (Python):

def main():
    import sys

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

    def dfs(A: list):
        nonlocal ans
        if len(A) == N:
            ans = max(ans, calc(A))
            return
        for v in range(A[-1] if A else 1, M + 1):
            A.append(v)
            dfs(A)
            A.pop()
    
    input = sys.stdin.readline

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

    ans = 0
    dfs([])
    print(ans)


main()

Solution (Python):

def main():
    import sys
    from itertools import combinations_with_replacement

    input = sys.stdin.readline

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

    ans = 0
    for pattern in combinations_with_replacement(range(1, M + 1), N):
        res = 0
        pattern = list(pattern)
        for a, b, c, d in lst:
            if pattern[b - 1] - pattern[a - 1] == c:
                res += d
        ans = max(ans, res)

    print(ans)


main()

Solution (Python):


def main():
    import sys

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

    def dfs(A: list):
        nonlocal ans
        if len(A) == N:
            ans = max(ans, calc(A))
        elif len(A) == 0:
            for nx in range(1, M + 1):
                dfs(A + [nx])
        else:
            for nx in range(A[-1], M + 1):
                dfs(A + [nx])

    input = sys.stdin.readline

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


main()

Solution (Python):


def main():
    import sys

    sys.setrecursionlimit(10 ** 8)
    
    def calc(A: list):
        score = 0
        for a, b, c, d in lst:
            if A[b - 1] - A[a - 1] == c:
                score += d
        return score

    def dfs(A: list):
        nonlocal ans
        if len(A) == N:
            ans = max(ans, calc(A))
        elif len(A) == 0:
            for nx in range(1, M + 1):
                dfs(A + [nx])
        else:
            for nx in range(A[-1], M + 1):
                dfs(A + [nx])

    input = sys.stdin.readline

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


main()

Solution (Python):
import copy

def cnt(a, m, i):
    if a[i] < m:
        a[i] += 1
    else:
        a = cnt(a, m, i-1)
        a[i] = copy.deepcopy(a[i-1])
    return a

def check(a, ab):
    score = 0
    for i in range(q):
        ai, bi = ab[i][0], ab[i][1]
        if a[bi] - a[ai] == ab[i][2]:
            score += ab[i][3]
    return score
  
n, m, q = map(int,input().split())
ab = []
for i in range(q):
    ab.append(list(map(int,input().split())))

a = [1] * (n+1)
a[0] = 0
ans = 0
while a[0] == 0:
    x = check(a, ab)
    ans = max(ans, x)
    
    a = cnt(a, m, -1)
print(ans)

Solution (Python):
import copy

def cnt(a, m, i):
    if a[i] < m:
        a[i] += 1
    else:
        a = cnt(a, m, i-1)
        a[i] = copy.deepcopy(a[i-1])
    return a

def check(a, ab):
    score = 0
    for i in range(q):
        ai, bi = ab[i][0], ab[i][1]
        if a[bi] - a[ai] == ab[i][2]:
            score += ab[i][3]
    return score
  
n, m, q = map(int,input().split())
ab = []
for i in range(q):
    ab.append(list(map(int,input().split())))

a = [1] * (n+1)
a[0] = 0
ans = 0
while a[0] == 0:
    x = check(a, ab)
    ans = max(ans, x)
    
    a = cnt(a, m, -1)
print(ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
n,m,q=map(int,input().split())
l=[i for i in range(1,m+1)]
ab=[list(map(int,input().split())) for _ in range(q)]
ans=0
for res in itertools.combinations_with_replacement(l, n):
    ans_r=0
    for i in range(q):
        a,b,c,d=ab[i]
        if c==res[b-1]-res[a-1]:
            ans_r+=d
    ans=max(ans,ans_r)
print(ans)

Solution (Python):

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


def dfs(x):
    if len(x) == N + 1:
        res = 0
        for a, b, c, d in X:
            if x[b] - x[a] == c:
                res += d
        return res

    res = 0
    for n in range(x[-1], M + 1):
        x.append(n)
        res = max(res, dfs(x))
        x.pop()
    return res


print(dfs([1]))

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

ans = 0
for pattern in combinations_with_replacement(range(1, M + 1), N):
    tmp_ans = 0
    pattern = list(pattern)
    for a, b, c, d in X:
        if pattern[b - 1] - pattern[a - 1] == c:
            tmp_ans += d
    ans = max(ans, tmp_ans)

print(ans)

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

Solution (Python):
n,m,q = map(int,input().split())
arr = [list(map(int,input().split())) for x 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):
import copy

N, M, Q = list(map(int, input().split()))
a = [0] * Q

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

mscore = 0

def createArray(num,arr):
    global mscore
    arr.append(num)
    if len(arr) < N:
        for i in range(num,M+1):
            arrr = copy.deepcopy(arr)
            createArray(i,arrr)
    else:
        score = 0
        for item in a:
            if arr[item[1]-1] - arr[item[0]-1] == item[2]:
                score += item[3]
        mscore = max(mscore, score)

for i in range(M):
    arr = []
    createArray(i+1,arr)

print(mscore)

Solution (Python):
import itertools







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






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


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



max_score = 0
for t in a:
    tot = 0
    for condition in conditions:
        if t[condition[1] - 1] - t[condition[0] - 1] == condition[2]:
            tot += condition[3]
    if tot > max_score:
        max_score = tot
print(max_score)

Solution (Python):
import math
def facts(n):
    ans = []
    for  i in range(1, int(math.sqrt(n)+1)):
        if(n%i==0):
            ans.append(i)
            ans.append(n//i)
    ans = sorted(ans)
    return ans


n,m,q =map(int, input().split())
qs = []
ans = 0
for i in range(q):
    arr= list(map(int, input().split()))
    qs.append(arr)
    
def calc(x):
    global ans
    tmp = 0
    for i in range(q):
        if(x[qs[i][1]-1]-x[qs[i][0]-1]==qs[i][2]):
            tmp+=qs[i][3]
    ans = max(ans, tmp)

def dfs(x):
    if(len(x)==n):
        calc(x)
    else:
        for i in range(x[-1], m+1):
            x.append(i)
            dfs(x)
            x.pop()
dfs([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], b[i] = a[i] - 1, b[i] - 1

ans = 0

def calc(x):
    global ans
    score = 0
    for i in range(q):
        if x[b[i]] - x[a[i]] == c[i]:
            score += d[i]
    ans = max(ans, score)

def dfs(x):
    if len(x) == n:
        calc(x)
        return

    for i in range(x[-1], m+1):
        x.append(i)
        dfs(x)
        x.pop()

dfs([1])
print(ans)