ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

6238: [2019CSP提高完善程序1]：匠人的自我修养

内存限制：256 MB 时间限制：2 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述

一个匠人决定要学习n个新技术，要想成功学习一个新技术，他不仅要拥有一定的经验值，而且还必须要先学会若干个相关的技术。学会一个新技术之后，他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值，给定他已有的经验值，请问他最多能学会多少个新技术。 

输入格式

输入第一行有两个数，分别为新技术个数n（1≤n≤10³），以及已有经验值（≤10^7）. 接下来n行。第i行的两个整数，分别表示学习第i个技术所需的最低经验值（≤10^7），以及学会第i个技术后可获得的经验值（≤10^4）。 接下来n行。第i行的第一个数mi（0≤mi＜n），表示第i个技术的相关技术数量。紧跟着m个两两不同的数，表示第i个技术的相关技术编号，输出最多能学会的新技术个数。 下面的程序已O（n^2）的时间复杂完成这个问题，试补全程序。

输出格式

输出最多能学会的新技术个数

输入样例 复制 

0

输出样例 复制 

0

分类标签