本蒟蒻只是在求一个更快速的方法，给了范围可能会让大家看了之后否定自己的代码，所以这次就不放出范围了，只是想求一个快速高效的算法来解决。大家可以当数据都在10以内，求最快的方法。

题目背景

小进是一个热爱作曲、不善于编程的孩子。一天，他又想编一首有 $m$ 个音符、有 $n$ 种不同音高的曲子。为了方便，将这 $n$ 种音高命名为 $1,2,3,4,...,n$ 。

小进想要让他的音乐尽可能好听，但又不会求解，于是找到了会编程的你。

题目描述

小进将会告诉你 $k$ 种不同的由 $2$ 个音符组成的旋律，还有这两个音符按某个顺序搭配后，乐曲的美妙度会增加相应的数。一首音乐，比如1 2 3，要拆成1 2和2 3两个由 $2$ 个音符组成的旋律。

还有一些由两个音符组成的旋律，小进没有给出，也就是这个旋律并不会增加美妙度，也不会减少。

你需要设计一个程序，输出所有可能中最高的美妙度，但是音符数量必须是 $m$ ，且为了避免重复单独，每一个 $2$ 个音符的旋律在这首乐曲中的数量是有限制的。

输入格式

第 $1$ 行输入 $3$ 个数，分别是 $n,m,k$ 。意义在上面已经给出。

接下来一共 $k$ 行，每一行 $4$ 个数，其中第 $i$ 行的 $4$ 个数分别为 $b_i,a_i,v_i,t_i$ ，它们表示第 $i$ 个由 $2$ 个音符组成的旋律是第 $a_i$ 个音高的音符在第 $b_i$ 个音高的音符后面（这两个音符是相邻的，即严格意义上的后面），这样的旋律的美妙度为 $v_i$ ，但在这首歌中只能出现 $t_i$ 次。

没有输入的旋律可以出现无数次。

输出格式

输出 $1$ 个数，即曲子美妙度的最大值。

输入输出样例

输入 # 1

9 9 9
6 5 10 1
5 3 8 1
3 5 6 1
5 2 9 1
2 1 8 1
4 7 -1 5
1 2 3 1
2 3 2 1
3 7 1 2

输出 # 1

47

样例说明：

6 5 3 5 2 1 2 3 7 或 6 5 2 1 2 3 5 3 7

数据范围：

（已被隐藏）

蒟蒻目前就想到用DP做的 $O(n^2mk)$ 的做法(t还是不太好处理)，这题要更快的方法才能过，求方法。

也求dalao指导优化，谢谢！