元素核心

题目描述

在一座远古遗迹中，你发现了 $G$ 个神秘的元素池。每个元素池中都漂浮着几种不同等级的能量核心。

考古笔记记载：由于物理排斥效应，每个元素池中最多只能取出一枚核心。

你的能量收集瓶容量为 $M$。每枚核心的属性如下：

• 占用收集瓶的体积 $w_{i,j}$。
• 核心蕴含的能量值 $v_{i,j}$。

请计算在不超过收集瓶容量的前提下，你最多能收集到多少能量值。

输入格式

第一行包含两个整数 $M$ 和 $G$，分别表示容量和元素池数量。

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

• 第一行一个整数 $N_i$，表示第 $i$ 个元素池中的核心数量。
• 接下来 $N_i$ 行，每行包含两个整数 $w_{i,j}$ 和 $v_{i,j}$。

输出格式

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

输入输出样例 #1

输入 #1

20 3
2
5 100
10 150
2
8 120
4 50
3
2 30
5 80
1 10

输出 #1

350

数据范围

对于 $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$。

建议

二刷