背景

嘟嘟答对了cai0715的问题，获得了需要的花粉。制造了充足的解药。击退了邪恶的小毒物。菌国又恢复了安定的生活。

描述

为了报答嘟嘟消灭病毒之举，微生物之王小A准备把景天得魔剑赠送给他。但是小A又不想白白的给他，准备让他用100000个金币来换（ps：这还是送？）。嘟嘟初来乍到，哪里拿得出这么多金币，但有的确想要到魔剑，便请求小A降低点价格。小A说：“嗯，如果你能替我拿到龙王的龙鳞，我可以只要90000；如果你能替我拿到龙王的龙角，我可以只要50000金币。”嘟嘟就跑到龙王那里，向他要龙鳞或龙角，龙王要他用金币换，或者替他拿到其他的东西，他就可以降低价格。嘟嘟于是又跑到了其他地方，其他人也提出了差不多得要求，要么直接用金币交换，要么找到他们想要的东西换得较低的价格。不过嘟嘟不必要用多样的东西换一样东西，因为不会获得更低得交换价格。

嘟嘟这下犯了难，但他又非常想得到魔剑。所以他只好想你求助，让他用最少的钱换到魔剑。

另外还要说的是，微生物王国的一些人们相互间都多少有点矛盾且每个人有个等级，每两个人间可能互相都有厌恶值（这个两个人互相的厌恶值相等，其中厌恶值等于两人的等级差）。所以厌恶值超过一定限制的两个人不会进行任何形式的交换。但是嘟嘟救助了这个世界，他们是都会同意和你交换的。但是如果你和某个人进行了交换，那么厌恶他的人就不会再和你交换了，因为他们认为这样是间接地和对方交换。因此你要考虑所有的情况以后给他提供一个最好的方案。为了方便起见，我们把所有要交换的物品从1到n进行编号。魔剑也看做一个物品，且编号总是1。每件物品都要有一个对应的价格p，所属的主人的等级为L，以及一系列的交换物Ti和该交换物所对应可以给的较低价格Vi。如果两个人的厌恶值超过了M，就不能进行“间接交易”。你必须根据给出的数据来计算出嘟嘟最少需要多少金币才能获得魔剑

格式

输入格式

输入第一行是两个整数M，N，依次表示厌恶值差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、其拥有者的等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和可以降低到的价格。

输出格式

输出最少需要的金币数。

样例1

样例输入1

1 4
10000 3 1
3 5000
1000 2 1
4 2000
3000 2 2
2 2000
4 100
50 2 0

样例输出1

5150

限制

各个测试点1s

提示

对于 50 的测试数据，1<=N<=5
对于 100% 的测试数据，1 <= N <= 100