问题1802--跑装备

1802: 跑装备

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

星星打游戏跑到某个公会,他想拿到屠龙刀,于是向会长购买,会长要100个金币,星星没有那么多金币,问是否能打折,会长说若能搞到大祭司的法器,只要50金币,若是搞到大祭司的靴子,就只要30金币,星星找到大祭司,大祭司讲若是从其他人可以搞到他想要的东西,法器之类的也可以降价,跑到其他人也是有这些要求。星星跑到的这个部落里,具有强烈的等级观念,会员等级差距超过一定限制M,则两个人之间不可以进行任何形式的直接交易。他是一个外来者可以直接跟任意等级的交易,但是如果他和某个等级的人进行了交易,再与等级差距超过M限值的人不会和他交易
会长的物品包括降价要求都是称为1号物品,其他人的物品都有编号,每个物品都有价格P,所有者的会员等级L,还有优惠价对应的物品Ti和优惠价Vi,会员直接交易等级差M,现在请您帮助算一下,星星怎么样能用最少的金币买到屠龙刀。

输入

第一行是两个整数N,M(1 <= N <= 100 )表示装备的总数等级差距限制
接下来按照编号从1到N依次给出了N个物品的描述。
每个物品的描述开头是三个非负整数P、L、X(X < N),依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V,分别表示优惠装备的编号和"打折价格"。

输出

花费最少的金额

样例输入

4 1
1000 3 2
2 800
3 500
100 2 1
4 200
300 2 1
4 20
5 2 0

样例输出

525

提示

先买第四件物品 再买第三件 然后买第一件物品

来源/分类

 

[提交] [状态]