[arc027_3]最高のトッピングにしような
问题描述
在我经常光顾的餐馆里，通过用餐可以获得门票。
门票有两种类型：必须与配料交换的特殊门票和普通门票。
这家餐馆有N种配料，配料i可以通过交换ti张门票获得。在这家餐馆中，可以通过组合门票来获得多种类型的配料，但不能多次获得相同的配料。
在交换过程中，特殊门票和普通门票都被视为1张门票，但交换所使用的门票必须至少包含一张特殊门票。例如，如果有一种配料可以用4张门票交换，那么有以下4种交换方法：
- 1张特殊门票和3张普通门票的组合。
- 2张特殊门票和2张普通门票的组合。
- 3张特殊门票和1张普通门票的组合。
- 4张特殊门票的组合。
此外，每种配料都有一个正整数值，表示获得该配料时的愉悦程度，记为hi。
今天是特别的一天，我想通过合理利用手中的门票来最大化获得配料的愉悦值总和。根据门票和配料的信息，编写一个程序来求解可能的最大愉悦值总和。
输入
输入通过标准输入以以下格式给出。
X Y N t1 h1 t2 h2 : tN hN
- 第一行包含两个整数X（1 ≤ X ≤ 300）和Y（0 ≤ Y ≤ 300），用空格分隔。这表示我一开始有X张特殊门票和Y张普通门票。
- 第二行包含一个整数N（1 ≤ N ≤ 300），表示配料的种类数。
- 第三行到第N+2行包含配料的相关信息，每行包含两个整数ti（1 ≤ ti ≤ 600）和hi（1 ≤ hi ≤ 5,000,000），用空格分隔。这表示配料i可以通过交换ti张门票获得，并且获得此配料可以获得的愉悦程度为hi。
部分分
本问题设置有部分分。
- 对于满足X ≤ 50、Y ≤ 50、N ≤ 50、ti ≤ 100（1 ≤ i ≤ N）的数据集1，如果能够求解正确，则给予30分。
- 对于没有附加限制的数据集2，如果能够求解正确，则额外给予70分。
输出
请输出可能的最大愉悦值总和，单独为一行。输出末尾要换行。
示例1
输入示例
3 5
4
3 30
3 40
5 60
7 80
输出示例
100
初始状态下，我有3张特殊门票和5张普通门票。通过以下交换，可以达到最大值100（= 40 + 60）。
- 用1张特殊门票和2张普通门票，交换得到配料2。配料2的愉悦度为40。
- 用2张特殊门票和3张普通门票，交换得到配料3。配料3的愉悦度为60。
这种方法消耗了3（= 1 + 2）张特殊门票和5（= 2 + 3）张普通门票，因此是可行的。
示例2
输入示例
3 3
4
3 30
3 40
5 60
7 80
输出示例
70
最佳选择是获得配料1和配料2。
示例3
输入示例
1 5
4
3 30
3 40
5 60
7 80
输出示例
60
最佳选择是获得配料3，并剩余1张门票。
示例4
输入示例
6 12
4
3 30
3 40
5 60
7 80
输出示例
210
可以获得所有配料。