题目描述

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

$a_1$ $b_1$ $c_1$ $d_1$

$:$

$a_Q$ $b_Q$ $c_Q$ $d_Q$

输出格式

输出按要求构造出来的序列的最高得分。

样例 #1

样例输入 #1

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

样例输出 #1

110

构造的序列 $A={1,3,4}$ ，最高分是 $110$ 。

样例 #2

样例输入 #2

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

样例输出 #2

357500

样例 #3

样例输入 #3

10 10 1
1 10 9 1

样例输出 #3

1

提示

对于 $100\%$ 的数据：

• 所有的数据都是整数
• $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$ )