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



Sample input:
3 4 3
1 3 3 100
1 2 2 10
2 3 2 10


Sample output:
110

Submission status: Runtime Error

Solution code:
import itertools

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

total = 0

memo = []
number = []
for i in range(m):
    number.append(i+1)
len = len(number)

for j in range((len+3-1)*(len+2-1)*(len)//6):
    memo.append(0)

a = list(itertools.combinations_with_replacement(number,n))
for i in range(q):
    num = list(map(int,input().split()))
    for j in range((len+3-1)*(len+2-1)*(len)//6):
        if int(a[j][num[1]-1])-int(a[j][num[0]-1]) == num[2]:
            memo[j] += num[3]
print(max(memo))

Submission status: Runtime Error

Solution code:
import itertools

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

total = 0

memo = []
number = []
for i in range(m):
    number.append(i+1)
len = len(number)

for j in range((len+3-1)*(len+2-1)*(len)//6):
    memo.append(0)

a = list(itertools.combinations_with_replacement(number,n))
for i in range(q):
    num = list(map(int,input().split()))
    for j in range((len+3-1)*(len+2-1)*(len)//6):
        if int(a[j][num[1]-1])-int(a[j][num[0]-1]) == num[2]:
            memo[j] += num[3]


print(max(memo))

Submission status: Runtime Error

Solution code:
import itertools

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

total = 0

memo = []
number = []
for i in range(m):
    number.append(i+1)
len = len(number)

for j in range((len+3-1)*(len+2-1)*(len)//6):
    memo.append(0)


for i in range(q):
    num = list(map(int,input().split()))
    for j in range((len+3-1)*(len+2-1)*(len)//6):
        a = list(itertools.combinations_with_replacement(number,n))
        if int(a[j][num[1]-1])-int(a[j][num[0]-1]) == num[2]:
            memo[j] += num[3]


print(max(memo))

Submission status: Runtime Error

Solution code:
word=input()

t= []
count=0
while True:
    t = input().split()
    if word in t:
        count=count+t.count(word)
    elif 'END_OF_TEXT' in t:
        break


print(count)
print(t)

Submission status: Runtime Error

Solution code:
n,m,q,*abcd=list(map(int, Input.split()))
a=[]
b=[]
c=[]
d=[]

ans = 0

for i in range(q):
    a.append(abcd.pop(0))
    b.append(abcd.pop(0))
    c.append(abcd.pop(0))
    d.append(abcd.pop(0))
    
def dfs(la):
    global ans
    if len(la)==n+1:
        sum_d=0
        #print(la)
        #print(ans)
        for i in range(q):
            if la[b[i]] - la[a[i]] == c[i]:
                sum_d += d[i]
        if sum_d > ans:
            ans = sum_d
        return
    
    la.append(la[-1])
    while(la[-1]<=m):
        dfs(la.copy())
        la[-1] += 1
        

dfs([1])
print(ans)

Submission status: Runtime Error

Solution code:
imporrt itertools
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
A=[0 for i in range(N)]
for i in itertools.combination_with_replacement(A,N):
  s=0
  for k in range(Q):
    if i[b[k]-1]-i[a[k]-1]==c[k]:
      s+=d[k]
  maxs=max(maxs,s)
      
print(maxs)

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0
A=[0 for i in range(N)]
for i in intertools.combination_with_replacement(A,N):
  s=0
  for k in range(Q):
    if i[b[k]-1]-i[a[k]-1]==c[k]:
      s+=d[k]
  maxs=max(maxs,s)
      
print(maxs)

Submission status: Runtime Error

Solution code:
n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
p=[]
sys.setrecursionlimit(10**6)
def dfs(x):
	if len(x)==n:
		p.append(x)
	else:
		for i in range(m-x[-1]+1):
			dfs(x+[x[-1]+i])
dfs([1])
# import itertools
# p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

Submission status: Runtime Error

Solution code:
n,m,q=map(int,input().split())
abcd=[]
for _ in range(q):
	a,b,c,d=map(int,input().split())
	abcd.append((a,b,c,d))
ans=0
p=[]
sys.setrecursionlimit(10**6)
def dfs(x):
	if len(x)==n:
		p.append(x)
	else:
		for i in range(n-x[-1]+1):
			dfs(x+[x[-1]+i])
dfs([1])
# import itertools
# p=itertools.combinations_with_replacement(range(1,m+1),n)
for x in p:
	r=0
	for i in range(q):
		if x[abcd[i][1]-1]-x[abcd[i][0]-1]==abcd[i][2]:
			r+=abcd[i][3]
	ans=max(ans,r)
print(ans)

Submission status: Runtime Error

Solution code:
n, m, q = list(map(int,input().split()))
a = []
b = []
c = []
d = []
e = [0] * n
scores = []
total_scores = []

for i in range(q):
  a0, b0, c0, d0 = list(map(int,input().split()))
  a.append(a0)
  b.append(b0)
  c.append(c0)
  d.append(d0)
  
def dfs(a, b, c, d, e, i):
  if i == n:
    score = 0
    for j in range(q):
      if e[b[j] - 1] - e[a[j] - 1] == c[j]:
        score += d[j]
        scores
    return scores
  
  for j in range(e[i - 1], 11):
    e[i] = j
    dfs(a, b, c, d, e, i + 1)
    
total_scores = dfs(a, b, c, d, e, 1)
print(max(total_scores))

Submission status: Runtime Error

Solution code:
vn,m,q=map(int,input().split())
lis=[]
for i in range(q):
    a,b,c,d=map(int,input().split())
    lis.append((a,b,c,d))
    
from itertools import combinations_with_replacement

co=list(combinations_with_replacement(range(1,m+1),n))

ans=0
for status in co:
    tmp_score=0
    for a,b,c,d in lis:
        if status[b-1]-status[a-1]==c:
            tmp_score+=d
    ans=max(ans,tmp_score)
print(ans)

Submission status: Runtime Error

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

for i in range(q):
  a0, b0, c0, d0 = list(map(int,input().split()))
  a.append(a0)
  b.append(b0)
  c.append(c0)
  d.append(d0)
  
def dfs(a, b, c, d, e, i):
  if i == 10:
    score = 0
    for j in range(q):
      if e[b[j] - 1] - e[a[j] - 1] == c[j]:
        score += d[j]
    return score
  
  for j in range(e[i - 1], 11):
    e[i] = j
    dfs(a, b, c, d, e, i + 1)
    
scores.append(dfs(a, b, c, d, e, 1))
print(max(scores))

Submission status: Runtime Error

Solution code:

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())

# 1～Mまでの数を複数回用いて、長さNの要素の部分列返す
#（combinations：複数使用なし、combinations_with_replacement：複数使用あり）
A = np.array(list(itertools.combinations_with_replacement(range(1, M + 1), N)))

n = len(A) # 組合せ総数
score = np.zeros(n) [0,0,...,0] # 0が n個のaraay

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())

Submission status: Runtime Error

Solution code:
a = input().split()
N = int(a[0])
M = int(a[1])
Q = int(a[2])
current = []
for i in range(Q):
    e = input().split()
    f = [int(i) for i in e]
    current.append(f)
import itertools

c = list(itertools.combinations_with_replacement(range(1, M + 1), N))
value_list = []
for item in c:
    value = 0
    for k in current :
        if item[k[1]]-item[k[0]]==k[2]:
            value+=k[3]
    value_list.append(value)
    
print(max(value_list))

Submission status: Runtime Error

Solution code:
#dfs試す
n,m,q=map(int, input().split( ))
qs=tuple(tuple(map(int, input().split( ))) for _ in range(q))
def dfs(ll):
    if len(ll)==n+1:
        sm=0
        for ai,bi,ci,di in qs:
            if ll[bi]-ll[ai]==ci:
                sm+=di 
        return sm
    res=[]
    for i in range(ll[-1]+1,m+1):#+1
        ll2=ll+[i]
        res.append(dfs(ll2))
    return(max(res))
l=[0]
print(dfs(l))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline
from itertools import combinations_with_replacement

def main():
    N, M, Q = map(int, readline().rstrip().split())
    P = [tuple(map(int, readline().rstrip().split())) for _ in range(Q)]
    ans = 0    
    for pair in combinations_with_replacement([i for i in range(1, M+1)], M):
        score = 0
        for a, b, c, d in P:
            if pair[b-1] - pair[a-1] == c:
                score += d
        ans = max(ans, score)
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

l = list(itertools.combinations_with_areplacement(range(1,M+1), N))

nax = 0
for x in l:
    score = 0
    for i in range(Q):
        if int(x[b[i]-1]) - int(x[a[i]-1]) == c[i]:
            score += d[i]
    nax = max(nax,score)

print(nax)

Submission status: Runtime Error

Solution code:
#import numpy as np
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
#matrix = np.array(matrix)
import itertools
ansscore = 0
combi = list(combinations_with_replacement(range(1,M+1),N))
for i in combi:
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    ansscore = score if score>ansscore else ansscore

print(ansscore)

Submission status: Runtime Error

Solution code:
#import numpy as np
N,M,Q=map(int, input().split())
matrix=[]
for _ in range(Q):
    c=list(map(int, input().split()))
    matrix.append(c)
#matrix = np.array(matrix)
import itertools
ansscore = 0
combi = list(combinations_with_replacement(range(1,M+1),N)
for i in combi:
    i = list(i)
    i.sort()
    score=0
    for l in matrix:
        a=l[0]
        b=l[1]
        c=l[2]
        d=l[3]
        if i[b-1]-i[a-1]==c:
            score+=d
    ansscore = score if score>ansscore else ansscore

print(ansscore)

Submission status: Runtime Error

Solution code:
from itertools import combinations as c
n, m, q = map(int, input().split())
arr = []
for i in range(q):
  l = [*map(int, input().split())]
  arr.append(l)
res = 0
for g in c(list(range(1, m+1)), n):
  f = 0
  for h in arr:
    if g[1] - g[0] == g[2]:
      f += g[3]
  res = max(res, f)
print(res)

Submission status: Runtime Error

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

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

dfs("1")
result = 0
for p in patterns:
  p = [int(i) for i in p]
  r = 0
  for q in Qs:
    if p[q[1]-1]-p[q[0]-1]==q[2]:
      r += q[3]
  #print(p, r)
  result = max([result, r])
print(result)

Submission status: Runtime Error

Solution code:

n, m , q = map(int, input().split())
 
l = []
for i in range(q):
  a,b,c,d = map(int, input().split())
  l.append((a,b,c,d))
max_score = 0
comb = [[1]]
while len(comb[0]) > 0:
  seed = comb.pop()
  if len(seed) == n:
    score = 0
    for j in l:
      if seed[j[1]-1]-seed[j[0]-1]==j[2]:
      
        score += j[3]
    if score > max_score:
      max_score = score
  else:
    for k in range(seed[-1], m+1):
      comb.append(seed.copy().append(k))
print(max_score)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np

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

A = np.array(list(itertools.combinations_with_replacemeent(range(1, M+1), N)))
s = np.zeros(len(A), np.int32)

for i in range(Q):
    a, b, c, d = map(int, input().split())
    s += d * (A[:, b-1] - A[:, a-1] == c)

print(s.max())

Submission status: Runtime Error

Solution code:
import math
import itertools

n, m, q = map(int, input().split(" "))
aL = []
_max = 0

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

li = []


def dfs(i, _n, p):
    if i == n:
        li.append(list(map(int, list(str(_n)))))
        return
    for j in range(p, m + 1):
        dfs(i + 1, _n * 10 + j, j)


if m != 1:
    for i in range(1, m + 1):
        dfs(1, i, i)
else:
    li = [[i] for i in range(1, n + 1)]

for t in li:
    if t[0] == 0:
        continue
    _sum = 0
    for a in aL:
        if t[a[1] - 1] - t[a[0] - 1] == a[2]:
            _sum += a[3]
    _max = max(_max, _sum)

print(_max)

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
a=[]
b=[]
c=[]
d=[]
for i in range(Q):
  ta,tb,tc,td=map(int,input().split())
  a+=[ta]
  b+=[tb]
  c+=[tc]
  d+=[td]
maxs=0

def suuretu(n,m):#n桁m以上
  if n>1:
    A=[]
    for i in range(1,9):
      for j in suuretu(n-1,i):
        A+=[10*i+j]
    return A
  else:
    A=[i for i in range(m,10)]
    return A
B=suuretu(N,1)
answer=0
for i in B:
  ans=0
  s=str(i)
  tmpl=[int(s[j]) for j in range(N)]  
  for k in range(Q):
    if tmpl[a[k]-1]-tmpl[b[k]-1]==c[k]:
      ans+=d[i]
  answer=max(answer,ans)
print(answer)

Submission status: Runtime Error

Solution code:
import math
import itertools

n, m, q = map(int, input().split(" "))
aL = []
_max = 0

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

li = []


def dfs(i, _n, p):
    if i == n:
        li.append(list(map(int, list(str(_n)))))
        return
    for j in range(p, m + 1):
        dfs(i + 1, _n * 10 + j, j)


if m != 1:
    for i in range(1, m + 1):
        dfs(1, i, i)
else:
    li = [[i] * m for i in range(1, n + 1)]

for t in li:
    if t[0] == 0:
        continue
    _sum = 0
    for a in aL:
        if t[a[1] - 1] - t[a[0] - 1] == a[2]:
            _sum += a[3]
    _max = max(_max, _sum)

print(_max)

Submission status: Runtime Error

Solution code:

List = []
def dfs(S):
    global N,M

    if len(S)==N:
        List.append(list(map(int, list(S))))
        return
    for i in range(1, M+1, 1):
        i = str(i)
        dfs(S+i)
    return

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

dfs("")
for i in range(1,M+1,1):
    L.append(i)

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

ans = 0
for l in List:
    temp = 0
    for q in range(Q):
        if (l[B[q]-1]-l[A[q]-1])==C[q]:
            temp = temp + D[q]
    ans = max(ans, temp)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
 
n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations, combinations_with_replacement
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Runtime Error

Solution code:
import math
n,m,q = map(int, input().split())
kumiQ =[]
for i in range(1,q+1):
	kumiQ.append(map(int, input().split())

                 
                 
kumiQ=[list(map(int, input().split())) for i in [0]*q]

#print(kumiQ[0][5])

Submission status: Runtime Error

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
 
n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations, combinations_with_replacement
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n, m, q = map(int, input().split(' '))
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
 
n, m, q = map(int, input().split())
vec = []
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
for i in range(1, m+1):
    for j in range(len(it)):
        vec.append(i)
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations(vec, len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations, combinations_with_replacement
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n, m, q = map(int, input().split())
a = []
b = []
c = []
d = []
for _ in range(q):
    i, j, k, l = map(int, input().split())
    a.append(i - 1)
    b.append(j - 1)
    c.append(k)
    d.append(l)
it = a + b
it = list(set(it))
na = []
nb = []
for i in range(q):
    for j in range(len(it)):
        if a[i] == it[j]:
            na.append(j)
        if b[i] == it[j]:
            nb.append(j)
ans = 0
for x in combinations_with_replacement(range(1, m+1), len(it)):
    cnt = 0
    for i in range(q):
        if x[nb[i]] - x[na[i]] == c[i]:
            cnt += d[i]
    #print(x, cnt)
    if ans < cnt:
        ans = cnt
print(ans)

Submission status: Runtime Error

Solution code:
 n, m, q = map(int, input().split())
 T = []
 for i in range(q):
     a, b, c, d = map(int, input().split())
     T.append((a-1, b-1, c, d))
 
 L = []
 def f(l):
     if len(l) == n+1:
         L.append(l[1:])
         return
     for i in range(l[-1], m + 1):
         f(l + [i])
	f([1])
 
 print(max(sum(d for a, b, c, d in T if l[b] - l[a] == c)) for l in L)

Submission status: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
s = list(list(map(int, input().split())) for _ in range(Q))

mx = 0
a = [1]*10

for s1 in range(1, M+1):
    a[0] = s1
    for s2 in range(s1, M+1):
        a[1] = s2
        for s3 in range(s2, M+1):
            a[2] = s3
            for s4 in range(s3, M+1):
                a[3] = s4
                for s5 in range(s4, M+1):
                    a[4] = s5
                    for s6 in range(s5, M+1):
                        a[5] = s6
                        for s7 in range(s6, M+1):
                            a[6] = s7
                            for s8 in range(s7, M+1):
                                a[7] = s8
                                for s9 in range(s8, M+1):
                                    a[8] = s9
                                    for s10 in range(s9, M+1):
                                        a[9] = s10
                                        
                                        cnt = 0
                                        for i in range(Q):
                                            si = s[i]
                                            if a[si[1]] - a[si[0]] == si[2]:
                                                cnt += si[3]
                                            mx = max(mx, cnt)
                                            
print(mx)

Submission status: Runtime Error

Solution code:
import numpy as np

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

A = np.sort(np.random.randint(1, m+1, n))


def calc_energy(A):
    energy = 0.
    for i in range(q):
        if (A[b[i]-1] - A[a[i]-1]) == c[i]:
            energy += d[i]
    return energy


T = 20000
temperature_init = 10
for t in range(T):
    A_prev = np.copy(A)
    energy_prev = calc_energy(A_prev)

    idx = np.random.randint(0, n)
    A[idx] = np.random.randint(1, m+1)
    energy = calc_energy(A)

    if np.random.rand() < (energy - energy_prev)/temperature:
        pass
    else:
        A = np.copy(A_prev)
    temperature  = temperature_init*(1/(1+t**4))

print(np.int(calc_energy(A)))

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest
import itertools

sys.setrecursionlimit(500*500*500)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m,q=map(int, readline().rstrip().split())

    aa=[0]*q
    bb=[0]*q
    cc=[0]*q
    dd=[0]*q

    for i in range(q):
        aa[i],bb[i],cc[i],dd[i]=map(int, readline().rstrip().split())

    max_score=0

    for a in itertools.combinations_with_replacement(list(range(1,m+1)),m):
        score=0
        for i in range(q):
            if (a[bb[i]-1]-a[aa[i]-1])==cc[i]:
                score+=dd[i]
        max_score=max(max_score,score)

    print(max_score)

    return
  
resolve()

Submission status: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
q_list = []

for i in range(Q):
    n_list = [int(x) for x in input().split()]
    q_list.append(n_list)



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

tem_max = 0
for A in A_list:
    q_max = 0
    for q in q_list:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            q_max += q[3]
    if tem_max < q_max:
        tem_max = q_max
print(tem_max)

Submission status: Runtime Error

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools

sys.setrecursionlimit(500*500)

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m,q=map(int, readline().rstrip().split())

    aa=[0]*q
    bb=[0]*q
    cc=[0]*q
    dd=[0]*q

    for i in range(q):
        aa[i],bb[i],cc[i],dd[i]=map(int, readline().rstrip().split())

    max_score=0
    for a in itertools.combinations_with_replacement(list(range(1,m+1)),m):
        score=0
        for i in range(q):
            if (a[bb[i]-1]-a[aa[i]-1])==cc[i]:
                score+=dd[i]
        max_score=max(max_score,score)

    print(max_score)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()


### ----------------
### ここまで 
### ----------------

Submission status: Runtime Error

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m,q=map(int, readline().rstrip().split())

    aa=[0]*q
    bb=[0]*q
    cc=[0]*q
    dd=[0]*q

    for i in range(q):
        aa[i],bb[i],cc[i],dd[i]=map(int, readline().rstrip().split())

    max_score=0
    for a in itertools.combinations_with_replacement(list(range(1,m+1)),m):
        score=0
        for i in range(q):
            if (a[bb[i]-1]-a[aa[i]-1])==cc[i]:
                score+=dd[i]
        max_score=max(max_score,score)

    print(max_score)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()


### ----------------
### ここまで 
### ----------------

Submission status: Runtime Error

Solution code:
import itertools

abcd = []
N,M,Q = map(int,input().split())
for i in range(Q):
    a,b,c,d = map(int,input().split())
    abcd.append([a,b,c,d])
  
A = (list(itertools.product(list(range(1,M+1)),repeat=N)))

ans = 0
for i in A: )
    _sum = 0
    for j in abcd: 
        if i[j[1]-1] - i[j[0]-1] == j[2]:
            _sum += j[3]
    if ans < _sum:
        ans = _sum
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys
imput = sys.stdin.readline

import numpy as np

def main():
    N, M, Q = map(int, input().split())
    I = [list(map(int, input().split())) for _ in range(Q)]
    A = np.array([M] * N)
    ans = []
    
    j = 1
    while True:
        if A[-1] == 1:
            break
        
        tmp = 0
        for i in I:
            a, b, c, d = i
            tmp += d if A[b-1] - A[a-1] == c else 0

        ans.append(tmp)

        if A[0] == 1:
            n = A[j]
            A[:j+1] = n - 1
            if n - 1 == 1:
                j += 1
        else:
            A[0] -= 1
            
    print(max(ans))    


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import itertools

def c165(n, m, q, adli):

    ans = 0
    li = list(itertools.combinations_with_replacement(range(1,M+1), n))
    for i in li:
        count = 0
        for a, b, c, d in adli:
            if i[b-1] - i[a-1] == c:
                count += d
        ans = max(ans, count)

    return ans

def main():
    n, m, q = map(int, input().split())
    adli = [list(map(int, input().split()))for i in range(q)]
    print(c165(n, m, q, adli))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    from itertools import combinations_with_replacement
    import sys
    input = sys.stdin.buffer.readline
    N, M, Q = (int(i) for i in input().split())
    T = [[int(i) for i in input().split()] for j in range(Q)]
    ans = 0
    for A in combinations_with_replacement(range(1, M+1), N):
        A.sort()
        cur = 0
        for a, b, c, d in T:
            if A[b-1] - A[a-1] == c:
                cur += d
        ans = max(ans, cur)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == M:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

    return max((solve(A + [i]) for i in range(A[-1], M + 1)), default=0)

print(solve([1]))

Submission status: Runtime Error

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

N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == M:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

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

print(solve([1]))

Submission status: Runtime Error

Solution code:
import itertools
N, M, Q = map(int, input().split())
for i in range(Q):
    q_list.append(list(map(int, input().split())))

q_list = []
final_score = 0
for A in itertools.combinations_with_replacement(range(1,11), N):
    score = 0
    for q in q_list:
        if A[q[1]-1] - A[q[0]-1] == q[2]:
            score += q[3]
        final_score = max([final_score, score])
print(final_score)

Submission status: Runtime Error

Solution code:
N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == M:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

    return max((solve(A + [i]) for i in range(A[-1], M + 1)), default=0)

print(solve([1]))

Submission status: Runtime Error

Solution code:
N, M, Q, *ABCD = map(int, open(0).read().split())

L = list(zip(*[iter(ABCD)] * 4))

def solve(A):
    if len(A) == M:
        return sum(d for a, b, c, d in L if A[b - 1] - A[a - 1] == c)

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

print(solve([1]))