成仙之路
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
有个蘑菇精想要成仙，但是他必须要收集 10000 个精灵宝石，不过他要是有花精灵的泪水，就只要 8000 个精灵宝石就可以了，或者如果他有花精灵的血滴，就只要 5000 个精灵宝石便可以成仙了。蘑菇精可以和森林里的其他精灵交换东西，但是修为等级差距过大的交换会影响修炼。
蘑菇精就跑到花精灵那里，向他索要泪水或血滴，花精灵要他用精灵宝石来换，或者替他弄来其他的东西，他可以降低价格。蘑菇精于是又跑到其他地方，其他精灵也提出了类似的要求，或者直接用精灵宝石换，或者找到其他东西就可以降低价格。不过蘑菇精没必要用多样东西去换一样东西，因为这不会得到更低的价格。
蘑菇精现在很需要你的帮忙，让他用最少的精灵宝石帮助他成仙。另外他要告诉你的是，在这个森林里，交换东西，修为差距超过一定限制的两个精灵之间不会进行任何形式的直接接触，包括交易，否则会影响修炼。
蘑菇精是外来精灵，所以可以不受这些限制。但是如果他和某个修为等级较低的精灵进行了交易，修为等级较高的的精灵有可能不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从 1 开始进行编号，成仙也看作一个物品，并且编号总是 1。每个物品都有对应的代价 P，主人精灵的修为等级 L，以及一系列的替代品 T_i 和该替代品所对应的“优惠” V_i。如果两个精灵修为等级差距超过了 M，就不能“间接交易”。你必须根据这些数据来计算出蘑菇精最少需要多少精灵宝石才能成仙。
输入格式
第一行是两个整数 M,N(1<= M<= 20, 1<= N<= 20000)，依次表示修为等级差距限制和物品的总数。接下来按照编号从小到大依次给出了 N 个物品的描述。每个物品的描述开头是三个非负整数 P,L,X（X<;N），依次表示该物品的代价、主人精灵的修为等级和替代品总数。接下来 X 行每行包括两个整数 T 和 V，分别表示替代品的编号和“优惠价格”。 (sum(X)<= 200000)。
输出格式
对于每个测试数据，在单独一行内输出最少需要的精灵宝石数。
样例
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 05250
20220820春季Level-5集训
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 5
- 开始于
- 2022-8-20 17:15
- 结束于
- 2022-8-30 17:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 14
