[ABC165C] Many Requirements

给你三个整数$N, M, Q$ 和 $Q$ 个要求 $a_i, b_i, c_i, d_i$。 让你构造一个长度为 $N$ 的数列 $A$ 满足 $1 \leq A_1 \leq A_2 \leq \cdots \leq A_N \leq M$。 对于一个数列 $A$ 会有一个得分，是满足 $A_{b_i}-A_{a_i}=c_i$ 的 $i$ 的 $d_i$ 的和。 现在要你构造一个数列使得其得分最高。 $2 \leq N \leq 10$ $1 \leq M \leq 10$ $1 \leq Q \leq 50$

[problemUrl]: https://atcoder.jp/contests/abc165/tasks/abc165_c 正整数 $ N $ , $ M $ , $ Q $ と、$ 4 $ つの整数の組 ( $ a_i $ , $ b_i $ , $ c_i $ , $ d_i $ ) $ Q $ 組が与えられます。 以下の条件を満たす数列 $ A $ を考えます。 - $ A $ は、長さ $ N $ の正整数列である。 - $ 1\ \leq\ A_1\ \leq\ A_2\ \le\ \cdots\ \leq\ A_N\ \leq\ M $ この数列の得点を、以下のように定めます。 - $ A_{b_i}\ -\ A_{a_i}\ =\ c_i $ を満たすような $ i $ についての、 $ d_i $ の総和 (そのような $ i $ が存在しないときは $ 0 $) $ A $ の得点の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ a_1 $ $ b_1 $ $ c_1 $ $ d_1 $ $ : $ $ a_Q $ $ b_Q $ $ c_Q $ $ d_Q $

$ A $ の得点の最大値を出力せよ。

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

110

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

357500

10 10 1
1 10 9 1

1

### 制約 - 入力は全て整数 - $ 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) $ ( $ i\ \neq\ j $ のとき) - $ 1\ \leq\ d_i\ \leq\ 10^5 $ ( $ i\ =\ 1,\ 2,\ ...,\ Q $ ) ### Sample Explanation 1 $ A\ =\ \{1,\ 3,\ 4\} $ のとき、この数列の得点は $ 110 $ となります。この条件の下では $ 110 $ より高い得点を持つ数列は存在しませんから、答えは $ 110 $ です。