时空裂缝

题目描述

时空工程师正在尝试修补一处巨大的时空裂缝。裂缝被划分为 $G$ 个不稳定区域，每个区域都需要投入一定的“稳定性粒子”来固化。

每个区域都有多种固化方案，但由于物理干涉，对于每个区域，你最多只能选择并执行一种固化方案。

你有 $M$ 点能量储备。每种方案的属性如下：

• 消耗的能量值 $w_{i,j}$。
• 产生的稳定性增益 $v_{i,j}$。

请计算出在有限的能量储备下，你能获得的最大稳定性增益是多少。

输入格式

第一行包含两个整数 $M$ 和 $G$，分别表示能量上限和区域数量。

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

• 第一行一个整数 $N_i$，表示第 $i$ 个区域的固化方案数。
• 接下来 $N_i$ 行，每行包含两个整数 $w_{i,j}$ 和 $v_{i,j}$。

输出格式

输出一个整数，表示在限制范围内能获得的最大稳定性增益。

输入输出样例 #1

输入 #1

50 3
2
10 30
20 40
2
15 35
25 60
2
20 50
10 25

输出 #1

140

样例 1 说明

区域 1 选 (10, 30)，区域 2 选 (25, 60)，区域 3 选 (10, 25)。和=45 $\le$ 50，总增益 115。 区域 1 选 (10, 30)，区域 2 选 (15, 35)，区域 3 选 (20, 50)。和=45 $\le$ 50，总增益 115. 重新检查最优情况。

数据范围

对于 $100\%$ 的数据，$1 \le M \le 5000$，$1 \le G \le 500$，$1 \le N_i \le 100$，$1 \le w_{i,j}, v_{i,j} \le 1000$。 注意：数据量较大，请确保算法效率。

建议

三刷