atcoder ABC165 C - Many Requirementsの勉強

・参考：
よくやる再帰関数の書き方〜 n 重 for 文を機械的に〜 - けんちょんの競プロ精進記録

・やったこと：参考記事の内容をpythonで勉強した。長さがNのリストAをDFSで全探索する。その時の得点(score)が一番高いものがansになる。

#参考：https://drken1215.hatenablog.com/entry/2020/05/04/190252
n,m,q=map(int,input().split())
a=[0 for _ in range(q)]
b=[0 for _ in range(q)]
c=[0 for _ in range(q)]
d=[0 for _ in range(q)]
for i in range(q):
  aq,bq,cq,dq=map(int,input().split())
  #aq,bqはインデックスになるので0からにする。
  aq-=1
  bq-=1
  a[i],b[i],c[i],d[i]=aq,bq,cq,dq
#得点  
def score(A):
  res=0
  for i in range(q):
    if A[b[i]]-A[a[i]]==c[i]:
      res+=d[i]
  return res

def dfs(A):
  if len(A)==n:
    return score(A)
  
  ans=0
  prev=A[-1] if len(A)>0 else 1  #len(A)>0のときprev=A[-1]、それ以外はprev=1。Aが単調増加の条件よりA[-1]より大きい値を試す必要があるので。
  for i in range(prev,m+1):
    A.append(i)
    ans=max(ans,dfs(A))   #スコアが最大のものをansにする。
    A.pop()
  return ans

print(dfs([]))