{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 某天超市搞活动,小明想买一个自己一直想买的电脑,平时需要7000,小明觉得太贵了。但活动当天,超市里的商品可以通过买其他商品获得优惠券。例如买一个键盘然后买电脑只需要5000,如果买一个鼠标买电脑只需要4000。同理,买其他商品也有这样的优惠活动。但商场出于某种目的,给每一件商品都标了等级,如果买了低于某个等级的商品,就不能够再买某些高级商品。\n \u003cbr\u003e为了方便,商店将每一件商品从1开始编号,电脑的编号为1.每一件商品都有对应的价格p,等级l,以及所对应的优惠商品Ki和优惠价格Ri。如果两件商品等级差超过D,就不能同时购买。小明想用最少的钱买到电脑。 \n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 第一行是两个整数D,t(1 \u0026lt;\u003d t \u0026lt;\u003d 100),分别代表等级的差距限制和商品的数量。接下来按照编号从1到t给出商品的描述。每个商品的描述开头是v、e、m(m \u0026lt; t),表示该物品的价格、商品的等级和对应优惠商品总数。接下来m行每行包括两个整数K和R,分别表示优惠商品的编号和对应商品优惠后价格。\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\"\u003e2 4\n7000 2 2\n2 5000\n3 4000\n500 1 0\n1000 2 1\n4 100\n30 2 0\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e4130\u003c/pre\u003e"}}]}