{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"会长东东想娶酋长的女儿,但酋长要求他给一定数额金钱的聘礼。除了金钱外,酋长也允许用部落里其他人的某物品加上一点钱作为聘礼。而其他人的物品也可以通过指定的另外一些人的某物品加上一些金钱获得。但是部落里的每个人有一个等级。整个交易过程涉及的人的等级只能在一个限定的差值内。问会长东东最少需要多少金钱才能娶到酋长女儿。假定每个人只有一个物品。\n"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 输入第一行是两个整数M,N(1 \u0026lt;\u003d N \u0026lt;\u003d 100),依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X(X \u0026lt; N),依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V,分别表示替代品的编号和\"优惠价格\"。\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 输出最少需要的金币数。\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e1 4\n10000 3 2\n2 8000\n3 5000\n1000 2 1\n4 200\n3000 2 1\n4 200\n50 2 0\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e5250\u003c/pre\u003e\n\n例:\n\n最高最低等级差不超过1,共4个物品\n\n酋长的女儿 等级3 要求现金10000元 或甲的物品+8000元 或乙的物品+5000元\n\n甲的物品 等级2 要求现金1000元 或丙的物品+200元\n\n乙的物品 等级2 要求现金3000元 或丙的物品+200元\n\n丙的物品 等级2 要求现金50元\n\n在这个例子中,最少花费方案是:买丙的东西(50)换乙的东西(+200)换酋长女儿(+5000)一共5250元。"}}]}