比赛场次 392
比赛名称 树立信心的模拟赛
比赛状态 已结束比赛成绩
开始时间 2017-09-01 19:00:00
结束时间 2017-09-01 22:00:00
开放分组 全部用户
注释介绍 全是水题,主要是树立信心,有问题联系QQ:1297879533
题目名称 凯伦和超市
输入输出 market.in/out
时间限制 2000 ms (2 s)
内存限制 512 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarOstmbh AAAAAAAAAA 2.423 s 383.43 MiB 100
Gravatar胡嘉兴 AWTTTTTTTT 16.009 s 0.36 MiB 10
Gravatar@@@ RRRRRRRRRR 0.001 s 0.36 MiB 0
GravatarShirry WWWWWWWWWW 1.016 s 191.97 MiB 0

凯伦和超市

★★★   输入文件:market.in   输出文件:market.out   简单对比
时间限制:2 s   内存限制:512 MiB

【题目描述】

在回家的路上,凯伦决定停在超市买些杂货。

她需要买很多商品,但由于她是学生,她的预算还是相当有限的。其实她只能花最高b美元。

超市里有n种商品,第i种商品价格为c[i]美元。当然,每种商品只能买一次。最近,超市一直在努力增加业务,作为忠实客户的凯伦,获得了n张优惠券,如果凯伦买了第i件商品,她可以用第i张优惠券来降低d[i]的价格。当然,如果不买相应的商品就无法使用优惠券。

然而,优惠券有一定限制:对于所有i≥2,为了使用第i张优惠券,凯伦也必须使用第xi张优惠券(这可能意味着使用更多的优惠券来满足该优惠券的要求)。凯伦想知道,用她的钱最多可以买多少商品。

【输入格式】

第一行输入包含两个整数n和b(1≤n≤5000,1≤b≤10^9),商店中的货物数量和凯伦的钱数。

接下来的n行描述以下项:

其中第i行开始是两个整数分别为次c[i]和d[i](1<=d[i]<c[i]<=10^9),表示第i个商品的价钱和用第i张优惠券买这个商品可以减少的价钱,如果i>=2,接下来是另一个整数x[i](1<=x[i]<i),表示第x[i]张优惠券应该先被使用。

【输出格式】

输出一行,一个整数,即凯伦能买到的最大的商品数。

【输入样例1】

6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5

【输出样例1】

4

【输入样例2】

5 10
3 1
3 1 1
3 1 2
3 1 3
3 1 4

【输出样例2】

5