题目描述

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

现在要你构造一个数列使得其得分最高。

输入

第一行三个整数$N,M,Q$

接下来一共$Q$行,每行$a,b,c,d$

输出

输出$A$的最大可能得分

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

110

样例解释

当 $A={1,3,4}$ 时，它的得分为 110。在这些条件下，没有序列的得分大于 110，所以答案是 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$ )