SP16048 PONY9 - Help Rarity Collect Crystals

Rarity 正在为即将到来的 Equestria 比赛收集特别的水晶。在一个宝石洞穴中，她发现了一批水晶。 Rarity 眼中的水晶有三个特征：颜色、反应性等级和时尚价值。她希望能够收集到水晶，使总时尚价值最大化。 由于一个袋子放不下所有的水晶，Rarity 带来了两个袋子。 然而，袋子容量并不是她面临的最大问题。关键在于这些水晶具有反应性。在洞穴中，它们相对稳定。但一旦放入袋子中并带出洞穴后，如果反应性等级过高，水晶会彻底分解，导致时尚价值消失殆尽。 水晶的反应机制有两种： 1. 当同一袋子中同颜色的水晶过多时，会引发分解。 2. 如果同一袋子中水晶的总反应性等级过高，也会导致分解。 不同颜色的水晶有不同的反应性限制。此外，有些颜色的水晶本身极不稳定，只要带出洞穴一定会分解。 Twilight Sparkle 曾经研究过这些水晶，并发明了一种方法防止水晶反应。这种材料虽然难以制造，但她还是为 Rarity 提供了一个特殊的袋子。这个袋子只能承装一颗水晶，但保证这颗水晶在袋子中不发生任何反应。 在这样的情况下，Rarity 需要你的帮助。

第一行输入一个整数 $T$，表示有多少组测试用例。 每组测试用例第一行有两个整数 $R$ 和 $C$： - $R$ 表示普通袋子中允许的最大反应性等级，超过则水晶会分解。 - $C$ 表示 Rarity 现在能看到的水晶颜色种类数。 接下来的 $C$ 行，每行表示如下格式：$L \ N \ r_1 \ v_1 \ r_2 \ v_2 \ \ldots \ r_N \ v_N$： - $L$ 是每种颜色在同一个袋子中最多可保存而不引起反应的水晶个数。 - $N$ 是当前种颜色水晶的数量。 - 接下来的 $2N$ 个数是成对出现的，每对代表一个水晶的反应性等级和时尚值。 测试用例是连续给出的，没有空行间隔（见示例输入）。

对每组测试用例，单独输出一行，表示 Rarity 能用她的袋子收集到的水晶的最大时尚总值。 ## 数据范围 - $1 \le R \le 100$ - $1 \le C \le 10$ - $0 \le L \le 3$ - $1 \le N \le 10$ 对于反应性等级 $r$ 和时尚值 $v$，均满足 $1 \le r, v \le 1000$。 注意，Rarity 的两个普通袋子足够大，可以装下任意数量的水晶。 **本翻译由 AI 自动生成**