题目描述

正整数 $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$ の得点の最大値を出力せよ。

题目大意

给你三个整数$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$

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$ です。