题目背景

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

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

题目描述

小进将会告诉你 $k$ 种不同的由 $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

数据范围：

$1\le b,a\le n\le88$ （因为乐谱只有 $88$ 个音符）

$0\le t\le m\le1500$

$0\le k\le7656$

$-10^6\le v\le10^6$

蒟蒻目前就想到 $O(n^3m^2)$ （还有问题）的做法，要运算 $1,533,312,000,000$ 次，要约 $1500S(25min)$ 才能运行完。可以注意到这题 $O(n^3m)$ 能过，求方法。

$O(n^3m^2)$ 代码还有缺陷，比如输入

4 7 4
1 4 2 2
4 3 2 2
3 1 2 2
1 2 3 1

时它会在上一个音符是 $1$ 时选用 1 2 。这样会避开正确答案。也求dalao指导优化。如果把每一种情况存进去，最差会使时空复杂度都乘上一个 $k$ 。所以实际上现在还是只有 $O(n^3m^2k)=O(n^5m^2)$ 算法。即使您只会优化到真正的 $O(n^3m^2)$ 水平，也请您留下讲解，谢谢！