(匠人的自我修养)一个匠人决定要学习 n 个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 n(1≤n≤103),以及已有经验值(≤107)。
接下来 n 行。第 i 行的两个整数,分别表示学习第 i 个技术所需的最低经验值 (≤107),以及学会第 i 个技术后可获得的经验值 (≤104)。
接下来 n 行。第 i 行的第一个数 mi(0≤mi<n),表示第 i 个技术的相关技术数量。紧跟着 m 个两两不同的数,表示第 i 个技术的相关技术编号,输出最多能学会的新技术个数。
下面的程序已 O(n2)的时间复杂完成这个问题,试补全程序。
② 处应填( )
threshold[i]>points
threshold[i]>=points
points>threshold[i]
points>=threshold[i]