{"trustable":false,"sections":[{"title":"Description","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n In our childhood life, we usually read piles of fancy books after school. Most of the parents also have the routine, such as reading a funny story before their child entered into their dreamland. Therefore, story books became another childhood memories for most of millennials.\n \u003cbr\u003eOnce, Imagine that you were reading a story about Columbus discovered the New Continent - North America. They came to an Indian tribe. But accidentally, one of the explorers of Columbus team fell in love with a native chief\u0027s daughter, so he went to the chief to ask for a marriage. The chief asked him to use 10000 gold coins as a bride gift before he promised to marry his daughter. But the explorer could not get so many gold coins, so he asked the chief to lower his request. The chief said, \"Well, if you can get the high priest\u0027s fur jacket for me, I can just ask for 8000 gold coins. And if you can get his crystal ball, it\u0027s only 5000 gold coins. \"After hearing this, the explorer went to the high priest and asked him for a fur jacket or a crystal ball. The high priest asked him to exchange gold coins or get something else for him. At the same time, he could lower the price. The explorer then went elsewhere, and others made similar requests, either to exchange gold coins directly or to find something else to lower the price. But the explorer didn\u0027t have to trade a variety of things for only one thing, because they maybe wouldn\u0027t get a lower price. The explorer now needs your help so that he can marry his sweetheart with the least amount of gold coins. \n \u003cbr\u003eWhat’s more that the explorer wants to tell you is the hierarchy restriction is very strict in this Indian tribe. There will be no direct contact, including transactions, between two individuals whose status gap exceeds a certain limit. Columbus team members are outsiders, so the explorer can be free from these restrictions. But if he trades with someone of lower status, the person of higher status will no longer trade with him. They think that it is equivalent to indirect contact, and vice versa. So you need to give him the best solution after considering all the circumstances.\n \u003cbr\u003eFor convenience, we put all the items to start numbering from 1, chief’s promise also considered as an item, and the number is always 1. Each item has a corresponding price P, the owner\u0027s status L, and a series of substitutes Ti and the substitutes corresponding to the \"discount\" Vi. If the gap between the two status exceeds M, it can not be \"indirect transaction\". Based on these data, you have to figure out how many gold coins the explorer needs at least in order to marry the chief\u0027s daughter. \n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n There are multiple test cases. For each test case:\n \u003cbr\u003eThe first line of each test case is two integers M, N (1 \u0026lt;\u003d N \u0026lt;\u003d 100), indicating the status gap restriction levels and the total number of items. Then, the description of N items is given in the order of number from small to large. The description of each item begins with three non-negative integers P, L and X (X \u0026lt; N) in one line, indicating the price of the item, the status of the owner and the total number of substitutes. The following next X lines consists of two integers, T and V, indicating the number of the substitute and the \"discount price\" respectively.\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n For each test case, output one line containing one integer, indicating the minimum number of gold coins needed.\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"}}]}