C

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : $300300$ points

Problem Statement

Given are positive integers $\mathrm{NN}$, $\mathrm{MM}$, $\mathrm{QQ}$, and $\mathrm{QQ}$ quadruples of integers ( ${\mathrm{aiai}}^{}$ , ${\mathrm{bibi}}^{}$ , ${\mathrm{cici}}^{}$ , ${\mathrm{didi}}^{}$ ).

Consider a sequence $\mathrm{AA}$ satisfying the following conditions:

• $\mathrm{AA}$ is a sequence of $\mathrm{NN}$ positive integers.
• $\mathrm{1\le A1\le A2\le \cdots \le AN\le M1\le A1\le A2\le \cdots \le AN\le M}$.

Let us define a score of this sequence as follows:

• The score is the sum of ${\mathrm{didi}}^{}$ over all indices $\mathrm{ii}$ such that ${\mathrm{Abi-Aai=ciAbi-Aai=ci}}^{}$. (If there is no such $\mathrm{ii}$, the score is $00$.)

Find the maximum possible score of $\mathrm{AA}$.

Constraints

• All values in input are integers.
• $\mathrm{2\le N\le 102\le N\le 10}$
• $\mathrm{1\le M\le 101\le M\le 10}$
• $\mathrm{1\le Q\le 501\le Q\le 50}$
• $\mathrm{1\le ai<bi\le N1\le ai<bi\le N}$ ( $\mathrm{i=1,2,...,Qi=1,2,...,Q}$ )
• $\mathrm{0\le ci\le M-10\le ci\le M-1}$ ( $\mathrm{i=1,2,...,Qi=1,2,...,Q}$ )
• $(ai,bi,ci)\ne (aj,bj,cj)(ai,bi,ci)\ne (aj,bj,cj)$ (where $\mathrm{i\ne ji\ne j}$)
• $\mathrm{1\le di\le 1051\le di\le 105}$ ( $\mathrm{i=1,2,...,Qi=1,2,...,Q}$ )

---

Input

Input is given from Standard Input in the following format:

$\mathrm{NN}$ $\mathrm{MM}$ $\mathrm{QQ}$
${\mathrm{a1a1}}^{}$ ${\mathrm{b1b1}}^{}$ ${\mathrm{c1c1}}^{}$ ${\mathrm{d1d1}}^{}$
$::$
${\mathrm{aQaQ}}^{}$ ${\mathrm{bQbQ}}^{}$ ${\mathrm{cQcQ}}^{}$ ${\mathrm{dQdQ}}^{}$

Output

Print the maximum possible score of $\mathrm{AA}$.

---

Sample Input 1 Copy

Copy

3 4 3
1 3 3 100
1 2 2 10
2 3 2 10

Sample Output 1 Copy

Copy

110

When $\mathrm{A=\{1,3,4\}A=\{1,3,4\}}$, its score is $110110$. Under these conditions, no sequence has a score greater than $110110$, so the answer is $110110$.

---

Sample Input 2 Copy

Copy

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 Copy

Copy

357500

---

Sample Input 3 Copy

Copy

10 10 1
1 10 9 1

Sample Output 3 Copy

Copy

1
因为M<=10，所以DFS遍历所有情况复杂度O(M!)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <deque>
#include <bitset>
#define ll              long long
#define PII             pair<int, int>
#define rep(i,a,b)      for(int  i=a;i<=b;i++)
#define dec(i,a,b)      for(int  i=a;i>=b;i--)
#define pb              push_back
#define mk              make_pair
using namespace std;
int dir[4][2] = { { 0,1 } ,{ 0,-1 },{ 1,0 },{ -1,0 } };
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979323846;
const int mod = 998244353;
const int N = 50 + 5;
//if(x<0 || x>=r || y<0 || y>=c)

inline ll read()
{
    ll x = 0; bool f = true; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = false; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f ? x : -x;
}

ll gcd(ll m, ll n)
{
    return n == 0 ? m : gcd(n, m % n);
}
ll lcm(ll m, ll n)
{
    return m * n / gcd(m, n);
}
ll m, n, q;
ll a[N], b[N], c[N], d[N];
vector<bool> vis(11, false);
ll ans = 0;
void dfs(vector<int> &v)
{
    if (v.size()-1 == n)
    {
        ll res = 0;
        rep(i, 1, q)
        {
            if (v[b[i]] - v[a[i]] == c[i])
                res += d[i];
        }
        ans = max(ans,res);
        return;
    }
    for (int i = 1; i <= m; i++)
    {
        if (v.back()<=i)
        {
            v.push_back(i);
            dfs(v);
            v.pop_back();
        }
    }
}
int main()
{
    cin >> n >> m >> q;
    rep(i, 1, q)
    {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }
    vector<int> v(1,0);
    dfs(v);
    cout << ans << endl;
    return 0;
}