比赛场次 | 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 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
Ostmbh | AAAAAAAAAA | 2.423 s | 383.43 MiB | 100 |
胡嘉兴 | AWTTTTTTTT | 16.009 s | 0.36 MiB | 10 |
@@@ | RRRRRRRRRR | 0.001 s | 0.36 MiB | 0 |
Shirry | WWWWWWWWWW | 1.016 s | 191.97 MiB | 0 |
在回家的路上,凯伦决定停在超市买些杂货。
她需要买很多商品,但由于她是学生,她的预算还是相当有限的。其实她只能花最高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]张优惠券应该先被使用。
输出一行,一个整数,即凯伦能买到的最大的商品数。
6 16 10 9 10 5 1 12 2 1 20 18 3 10 2 3 2 1 5
4
5 10 3 1 3 1 1 3 1 2 3 1 3 3 1 4
5