問題文
在我最喜欢的餐厅,吃饭就能拿到票。
门票包括需要兑换配料的特价票和普通票。 2 类型存在。
这家店有 N 配料有多种类型。 i 是 可以通过兑换t_i 门票获得。在这家店,你可以组合门票来获得多种类型的配料,但你不能多次获得相同的配料。
兑换时,不区分特价票和普通票。 1 不过,用于兑换的券对于每种配料都有一张专用券。 1 。例如 如果有可以兑换 4 门票的配料,请执行以下操作: 4 有几种可能的交换方法。
- 特价票 1 和普通票 3 块的组合。 仅由
- 特价票 2 和普通票 2 块的组合。 仅由
- 特价票 3 和普通票 1 块的组合。 仅由
- 特价票 4 块组成的组合。
每个配料都有一个代表幸福的正整数,并且 当我得到 i 时我是多么高兴 h_i 。
今天是一个特殊的日子,所以我想充分利用我现有的门票,最大限度地享受我获得的配料的总乐趣。创建一个程序,从门票和顶部信息中找到最大可能的幸福总价值。
入力
输入是按以下格式从标准输入给出的。
X Y N t_1 h_1 t_2 h_2 : t_N h_N
- 1 行显示您拥有的票数。 2 整数 X (1 ≦ X ≦ 300) 和 在 Y (0 ≦ Y ≦ 300) 用空格分隔。首先这是特价票。 X 普通票 表示您有 Y 。
- 2 行包含一个表示顶部类型数量的整数。 N (1 ≦ N ≦ 300) 。 来自行
- 3 从行 N 行表示有关配料的信息。 2 整数 t_i (1 ≦ t_i ≦ 600), h_i (1 ≦ h_i ≦ 5,000,000) 用空格分隔。这是顶饰 i 是票 兑换 t_i 即可获得,获得后获得的快乐为 h_i 。
部分点
针对该问题设置了部分分数。 满足
- X ≦ 50, Y ≦ 50, N ≦ 50, t_i ≦ 100 (1 ≦ i ≦ N) 的数据集 如果您正确回答 1 ,30 点。
- 没有附加约束的数据集 如果您对 2 的回答正确,除上述之外, 70 点。
出力
幸福的最大可能总价值是 1 行输出。还在输出末尾添加换行符。
入力例1
3 5 4 3 30 3 40 5 60 7 80
出力例1
100
初始状态下,特价票为 我有 3 普通票 表示您有 5 。例如,如果执行以下交换,则最大值 100 (= 40 + 60) 可以实现。
- 配料 2 (如果票是 3 需要门票) 通过与 1 和普通票 2 交换获得。配料 2 的喜悦 40 。
- 配料 3 (如果票是 5 需要门票) 通过与 2 和普通票 3 交换获得。配料 3 的喜悦 60 。
此方法使用特价票。 3 (= 1 + 2) 普通票 表示您有 5 (= 2 + 3) 这是一个消耗碎片的方法,所以是可以的。
入力例2
3 3 4 3 30 3 40 5 60 7 80
出力例2
70
配料 1 和配料 最好获得 2 。 获取您的
入力例3
1 5 4 3 30 3 40 5 60 7 80
出力例3
60
配料 3 并获取门票 1 最好有多余的床单。
入力例4
6 12 4 3 30 3 40 5 60 7 80
出力例4
210
你可以获得所有的配料。