← 返回题目列表

AtCoder · abc165_c

C. 许多要求

中文机器翻译题面 查看原题

分数: 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