题目描述

需要构造一个长度为 $N$ 的不下降整数数列 $A_1, A_2, \ldots, A_N$，满足 $1 \le A_1 \le A_2 \le \cdots \le A_N \le M$。

数列还需满足 $Q$ 条得分条件：第 $i$ 条包含四个整数 $a_i, b_i, c_i, d_i$，若 $A_{b_i} - A_{a_i} = c_i$，则该条件为这个数列贡献 $d_i$ 分。一个数列的得分为所有满足条件的得分之和。

求所有合法数列中得分的最大值。

输入格式

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

接下来 $Q$ 行，每行输入四个整数 $a_i, b_i, c_i, d_i$，描述一条得分条件。

输出格式

输出一个整数，表示得分的最大值。

样例 1

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

110

样例 1 解释

取 $A = (1, 3, 4)$：条件 1 满足（$A_3 - A_1 = 3$），得 $100$ 分；条件 2 满足（$A_2 - A_1 = 2$），得 $10$ 分；条件 3 不满足（$A_3 - A_2 = 1 \ne 2$）。总分为 $110$，可以证明这是最大值。

样例 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

357500

样例 3

10 10 1
1 10 9 1

1

数据范围

• $2 \le N \le 10$，$1 \le M \le 10$，$1 \le Q \le 50$；
• $1 \le a_i < b_i \le N$，$0 \le c_i \le M - 1$，$1 \le d_i \le 10^5$；
• 任意两个条件的 $(a_i, b_i, c_i)$ 三元组互不相同；
• 所有输入均为整数。

本题共 25 个测试点，每个测试点 4 分，按测试点独立计分。

特殊性质 A：所有条件均满足 $c_i = 0$。