昂贵的聘礼
题目描述
年轻的探险家来到了一个印第安部落，他爱上了酋长的女儿，向酋长求亲。酋长要求他用10000个金币作为聘礼，或者用某些物品替代来降低价格。探险家发现，部落里的每个人都有类似的要求：要么直接用金币买自己的物品，要么用其他指定的物品替代来获得优惠价格。
不过，部落里等级观念森严：地位差距超过限制M的两个人之间不能进行任何形式的直接或间接交易。探险家作为外来人，可以不受限制，但如果他和某个地位较低的人交易了，地位较高的人就不会再和他交易（反之亦然）。因此，探险家只能选择一个连续的等级区间，所有与他交易的人的等级都必须在这个区间内。
请你帮助探险家计算出，他最少需要多少金币才能娶到酋长的女儿。为了方便，我们把所有物品从1开始编号，酋长的允诺（即娶到女儿的“物品”）编号总是1。
输入格式
第一行包含两个整数M和N，依次表示地位等级差距限制和物品的总数。
接下来按照编号从小到大依次给出N个物品的描述：
- 每个物品的描述开头是三个非负整数P、L、X，依次表示该物品的直接购买价格、主人的地位等级、替代品的总数。
- 接下来X行，每行包含两个整数T和V，表示可以用编号为T的物品作为替代品，此时购买该物品的优惠价格为V。
输出格式
输出一个整数，表示探险家最少需要的金币数。
样例 #1
样例输入 1
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
样例输出 1
5250