魔法卷轴

题目描述

作为一名见习法师，你正在筹备一场魔法表演。你需要从 $G$ 种不同的魔法流派中挑选卷轴。

这次表演非常特殊：对于每一类流派，你必须且只能挑选该类下的一张卷轴。

你有 $M$ 点法力值上限。每张卷轴的法力消耗为 $w_{i,j}$，获得的效果值为 $v_{i,j}$。

请计算出在每一类都恰好选一张的前提下，法力消耗不超过 $M$ 时能获得的最大总效果值。如果无论如何都无法满足“每类各选一张”且不超法力上限的条件，请输出 -1。

输入格式

第一行包含两个整数 $M$ 和 $G$，分别表示总法力值和卷轴流派数。

接下来有 $G$ 组数据，每组数据的格式如下：

• 第一行一个整数 $N_i$，表示第 $i$ 类卷轴的可选数量。
• 接下来 $N_i$ 行，每行包含两个整数 $w_{i,j}$ 和 $v_{i,j}$。

输出格式

输出一个整数。如果存在满足条件的方案，输出最大效果值，否则输出 -1。

输入输出样例 #1

输入 #1

10 2
2
5 10
6 15
2
5 20
4 12

输出 #1

30

样例 1 说明

组 1 选 (5, 10)，组 2 选 (5, 20)，和=10，值=30。 OK. 组 1 选 (6, 15)，组 2 无法选（最小 4，和为 10，OK，和=10，值=27）。 组 1 选 (5, 10)，组 2 选 (4, 12)，和=9，值=22。 最优为 30。

数据范围

对于 $100\%$ 的数据，$1 \le M \le 1000$，$1 \le G \le 50$，$1 \le N_i \le 50$，$1 \le w_{i,j}, v_{i,j} \le 1000$。

建议

二刷