AT_arc027_3.[ARC027C] 最高のトッピングにしような

在我常去的一家餐馆里，用餐可以获得兑换券。

兑换券有两种类型：一种是提供额外功能的“特殊兑换券”，另一种是“普通兑换券”。

这家餐馆提供 $N$ 种配料，你可以用 $t_i$ 张票券换得每种配料 $i$。在组合兑换中，同一种配料不可重复获取。兑换时，尽管两种类型的兑换券等值，但需保证每种配料的兑换至少包含一张“特殊兑换券”。例如，若某种配料需要 4 张票券，有以下 4 种兑换组合：

• 1 张特殊兑换券和 3 张普通兑换券。
• 2 张特殊兑换券和 2 张普通兑换券。
• 3 张特殊兑换券和 1 张普通兑换券。
• 全用 4 张特殊兑换券。

每种配料都有各自的“快乐值”，用 $h_i$ 表示获取配料 $i$ 时的快乐值。

今天是个特别的日子，我希望通过合理利用现有的兑换券，最大化兑换配料带来的总快乐值。请设计一个程序，计算出在当前的票券和配料信息下，能够获取的最大快乐值。

输入由标准输入提供，格式如下：

$X$ $Y$ $N$ $t_1$ $h_1$ $t_2$ $h_2$ : $t_N$ $h_N$

• 第一行有两个整数 $X$ 和 $Y$（$1 \leq X \leq 300$，$0 \leq Y \leq 300$），分别表示初始持有的特殊兑换券数和普通兑换券数。
• 第二行有一个整数 $N$（$1 \leq N \leq 300$），表示配料种类数。
• 接下来的 $N$ 行中，每行包含两个整数 $t_i$ 和 $h_i$（$1 \leq t_i \leq 600$，$1 \leq h_i \leq 5,000,000$），分别表示配料 $i$ 需要的票券数和对应的快乐值。

输出可能获得的最大快乐值，以一个整数形式输出。记得在最后加上换行。

部分得分

题目设有部分得分：

• 对于数据集 1，满足条件 $X \leq 50$，$Y \leq 50$，$N \leq 50$，$t_i \leq 100$ 的正确解答可以获得 30 分。
• 对于没有额外限制的通用数据集 2，正确解答可以获得 70 分。

样例解释

• 初始有 3 张特殊兑换券和 5 张普通兑换券。通过以下组合可以得到最大快乐值 100（即40 + 60）：

  • 使用 1 张特殊兑换券和 2 张普通兑换券兑换配料 2（需 3 张票券），获得快乐值 40。
  • 使用 2 张特殊兑换券和 3 张普通兑换券兑换配料 3（需 5 张票券），获得快乐值 60。
    这个组合用掉了 3 张特殊和 5 张普通兑换券，是可行的。

• 最优选择是获取配料 1 和配料 2。

• 选择配料 3，并留下一张票券，是最优解。

• 可以获取所有的配料。

本翻译由 AI 自动生成