装备选配

题目描述

在一款 RPG 游戏中，你的角色拥有 $M$ 个金币。商城里有 $G$ 种类型的装备（如武器、防具、饰品等）。

公会规定：为了职业平衡，每一种类型的装备中你最多只能购买一件。

已知每种属性的装备都有若干个具体的候选项：

• 第 $i$ 类装备的第 $j$ 个选项价格为 $w_{i,j}$。
• 该选项能提供的属性增益为 $v_{i,j}$。

请计算在金币限额内，角色能获得的最大属性增益总和。

输入格式

第一行包含两个整数 $M$ 和 $G$，分别表示总金币和装备类型数。

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

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

输出格式

输出一个整数，表示能够获得的最大增益总和。

输入输出样例 #1

输入 #1

45 3
2
10 10
20 20
2
15 17
8 10
2
20 25
10 12

输出 #1

52

数据范围

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

建议

一刷