P2967 [USACO09DEC] Video Game Troubles G

农夫约翰的奶牛们非常喜欢玩电子游戏！FJ 发现，在玩了这些游戏后，他的奶牛产的奶比平时多得多，这肯定是因为快乐的奶牛产奶更多。 然而，奶牛们对于哪个是最好的游戏机存在分歧。一头奶牛想买 Xbox 360 来玩《光环 3》；另一头想买任天堂 Wii 来玩《任天堂明星大乱斗》；第三头想在 PlayStation 3 上玩《合金装备 4》。FJ 想购买一些游戏机（每种不超过一台）和游戏（每种不超过一款并在给定预算的限制内），以帮助他的奶牛产出最多的牛奶，从而养育更多的孩子。 FJ 调查了 $N$ 台游戏机（$1 \leq N \leq 50$），每台游戏机的价格为 $P_i$（$1 \leq P_i \leq 1000$），以及独占发布于该游戏机的游戏数量 $G_i$（$1 \leq G_i \leq 10$）。当然，奶牛必须先拥有这台游戏机，才能购买该游戏机独占的任何游戏。每款游戏都有一个游戏价格 $GP_j$（$1 \leq GP_j \leq 100$）和一个生产值（$1 \leq PV_j \leq 1,000,000$），表示奶牛在玩游戏后会产出多少牛奶。最后，农夫约翰有一个预算 $V$（$1 \leq V \leq 100,000$），这是他最多能花的钱。帮助他最大化他购买的游戏的生产值之和。 考虑一个例子，$N=3$ 台游戏机，预算 $V=800$ 美元。 第一台游戏机价格为 $300$ 美元，并有两个游戏，价格分别为 $30$ 美元和 $25$ 美元，生产值如下所示： | 游戏编号 | 价格 | 生产值 | |:-:|:-:|:-:| |$1$|\$$30$|$50$| |$2$|\$$25$|$80$| 第二台游戏机价格为 $600$ 美元，只有一个游戏： | 游戏编号 | 价格 | 生产值 | |:-:|:-:|:-:| |$1$|\$$50$|$130$| 第三台游戏机价格为 $400$ 美元，有三个游戏： | 游戏编号 | 价格 | 生产值 | |:-:|:-:|:-:| |$1$|\$$40$|$70$| |$2$|\$$30$|$40$| |$3$|\$$35$|$60$| 农夫约翰应该购买游戏机 $1$ 和 $3$，游戏机 $1$ 的游戏 $2$，以及游戏机 $3$ 的游戏 $1$ 和 $3$，以最大化他所购买游戏的生产值。该值为 210： ```cpp 生产值 预算: $800 游戏机 1 -$300 游戏 2 -$25 80 游戏机 3 -$400 游戏 1 -$40 70 游戏 3 -$35 60 ------------------------------------------- 总计: 0 (>= 0) 210 ```

输入第 $1$ 行为两个用空格分隔的整数：$N$ 和 $V$ 第 $2$ 到 $N+1$ 行：第 $i+1$ 行描述了游戏机 $i$ 的价格 $P_i$ 和其独占的游戏数量 $G_i$，接下来后面有 $G_i$ 对用空格分隔的整数 $GP_j$ 和 $PV_j$，描述其独占的各款游戏的信息。

输出 $1$ 个整数，表示农夫约翰在他的预算内可以获得的最大生产值。

（由 ChatGPT 4o 进行翻译）