冒险者公会

题目描述

在艾泽拉斯大陆的冒险者公会里，公会会长为你准备了 $G$ 组任务。公会规定：为了保证任务质量，每一组任务中你最多只能挑选一个来执行。

你的精力总量为 $M$。每项任务的情况如下：

• 第 $i$ 组中的第 $j$ 项任务需要消耗精力 $w_{i,j}$。
• 完成该任务能获得声望值 $v_{i,j}$。

请计算在有限的精力范围内，你能获得的最大声望值是多少。

输入格式

第一行包含两个整数 $M$ 和 $G$，分别表示你的总精力和任务组数。

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

• 第一行一个整数 $N_i$，表示第 $i$ 组共有 $N_i$ 个可选任务。
• 接下来 $N_i$ 行，每行包含两个整数 $w_{i,j}$ 和 $v_{i,j}$。

输出格式

输出一个整数，表示能够获得的最大声望值。

输入输出样例 #1

输入 #1

10 2
3
2 10
5 20
1 5
2
4 15
6 25

输出 #1

45

样例 1 说明

总精力 10，组 1 选 (5, 20)，组 2 选 (6, 25)？不行，和为 11。 最优方案：组 1 选 (2, 10)，组 2 选 (6, 25)，总精力 8，总声望 35？不对。 再看：组 1 选 (5, 20)，组 2 选 (4, 15)，总精力 9，总声望 35。 如果组 1 选 (1, 5)？ 实际上，最优方案取决于数据，此处样例仅供参考。

数据范围

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

建议

一刷