Quelling Blade#3094
Mr. Sheep has lost himself in a computer game. In this game, he plays the part of a superhero fighting against evil. Equipment is very important in this game, and Mr. Sheep thinks the Quelling Blade is the most powerful weapon.
Each type of weapon costs the hero some amount of money and provides benefits. If the hero buys two weapons (regardless of whether they are the same type), the benefit values are added. For example, if the hero buys weapons with benefit values and , the total benefit value will be 8=3+5.
Each weapon may have certain requirements. If the hero wants to buy a certain weapon, he may first need to have some other weapons. For example, if the hero wants to buy a "Divine Rapier," he must acquire a "Demon Edge" and a "Sacred Relic". Of course, if he wants to buy a second "Divine Rapier," he must buy another "Demon Edge" and another "Sacred Relic". Note that an existing weapon will not disappear after a trade. Also, a weapon may require multiple weapons of the same type. Furthermore, a weapon type is required by at most one other weapon type.
The hero is busy fighting and has no time to earn money. Fortunately, the game gives the hero coin per second. Therefore, if the hero wants to buy a "Quelling Blade," the minimum total time required can be easily calculated.
Mr. Sheep is a perfectionist. He wants to obtain the "Quelling Blade" as quickly as possible, and also optimize every second of the game. He defines the utility of the game as the sum of the benefit values the hero has at each second. The utility is calculated from the start of the game until the second the hero gets the "Quelling Blade," exclusively. You may refer to the samples for clarification. In other words, you must determine a way to purchase the weapons for the hero that minimizes the total time to acquire the "Quelling Blade" and maximizes the utility of the game.
There are multiple test cases, and the number of test cases is given in the first line of the input. Most cases are relatively small.
For each test case, the first line contains a single integer representing the number of different weapon types (1 \le N \le 1000).
The following lines describe the weapons. For each weapon, the first line contains two integers and — the benefit value and the cost of this weapon type (1 \le B, C \le 2^{31}-1). Then the next line contains a single integer , the number of requirements for this weapon. The next lines each contain two integers and , indicating this weapon requires weapons of type with index .
Weapon indices go from to . "Quelling Blade" is the first weapon type. You may assume that the total number of weapons required for the "Quelling Blade" is less than . Also, note that the "Quelling Blade" can be obtained in finite game time, and one weapon type is required by at most one other weapon type.
For each test case, output a single integer denoting the optimal utility. You may assume that the answer fits in a -bit signed integer.
Esempio 1