分数: 300 点
问题陈述
给定的是正整数 N, M, Q,和 Q 整数的四元组 ( a_i , b_i , c_i , d_i ).
考虑一个序列 A 满足以下条件:
- A 是一系列 N 正整数。
- 1 \leq A_1 \leq A_2 \le \cdots \leq A_N \leq M.
让我们定义这个序列的分数如下:
- 分数是以下各项的总和 d_i 所有指数 i 这样 A_{b_i} - A_{a_i} = c_i。 (如果没有这样的 i,得分为 0.)
找出以下的最大可能分数 A.
约束
- 输入中的所有值都是整数。
- 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 )
输入
输入由标准输入按以下格式给出:
N M Q a_1 b_1 c_1 d_1 : a_Q b_Q c_Q d_Q
输出
打印最大可能分数 A.
示例输入 1
3 4 3 1 3 3 100 1 2 2 10 2 3 2 10
示例输出 1
110
当 A = \{1, 3, 4\},其得分为 110。在这些条件下,没有序列的分数大于 110,所以答案是 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
示例输出 2
357500
示例输入 3
10 10 1 1 10 9 1
示例输出 3
1