After computers have been invented, maybe computer games are one of the most important application of computers in our lives. The fascinating image, the lovely voice and the attractive plot have made those who are called ‘games fans’ wallowed in computer game deeply. Although nowadays the most advanced computer technologies in the world are used in computer games, ‘game fans’ are not always satisfied with the games, especially their prices. The more fasinating image, the lovelier voice, the more attractive plot the computer game has, the higher price it has. And what’s more, it requires ‘game fans’ to purchase the more advanced (which means the more expensive) equipments. As you know, not every game fan has a large fortune. Facing various hardwares and softwares in computer games, fans will be at a loss as they want to make a decision to buy some of them. But unfortunately, fans have to purchase corresponding hardwares to play specail softwares. For instance, “Mario Bro.” is one of Nintendo Incorporation’s software products, and only those who have “Family Computer” (which is one of Nintendo Incorporation’s hardware products) can play it. So game fans have to buy “Family Computer” before they want to buy “Mario Bro.”. Here is another instance about “Duck Hunter” which is another game of Nintendo Incorporation. To play “Duck Hunter”, game fans have to buy “Laser Gun” which is specially designed for “Family Computer” by Nintendo Incorporation. Neither those who have “Family Computer” and “Duck Hunter” but without “Laser Gun”, nor those who have “Laser Gun” and “Duck Hunter” but without “Family Computer” can play the game. And if a game fan has “Family Computer”, he can play any games designed for “Family Computer” without to purchase another “Family Computer”. For example, “Mario Bro.” and “Mario Bro. II” are both designed for “Family Computer”, those who have a “Family Computer” could enjoy themselves fully in playing “Mario Bro.” and “Mario Bro.II”. Finally, since game fans who have special hardwares and softwares have fully enjoyed themselves in playing corresponding computer games, it wouldn’t make any sense for them to buy the same hardware or the same software. After all, the same hardware or the same software will not bring game fans the additional pleasure. In this problem, you will be given the description about a game fan, including his cash and the detailed list of the hardwares and the softwares he wants to buy. The list includes the name of the hardwares and the softwares, the equipments they depend on, their prices and the pleasure they will bring to the fan. It’s unlucky that the fan couldn’t buy all the hardwares and the softwares in the list, for his cash is limited. So you are required to write a program to help him. Your program should calculate the maximum pleasure the fan could get and the cash he would pay for the corresponding pleasure. Undoubtly, the fan should have the means to pay for the pleasure. a) Your program should make a decision for each of the item in the detailed list whether buy or not, but should not buy the same item twice or more times. That is, each item in the list should be bought at most once. b) if some items in the list aren’t bought, these items wouldn’t bring any pleasure to the fan. And also, other items which depend on those wouldn’t bring the fan any pleasure either. c) You may assume that such condition or the similar condition will not take place: in the detailed list, item A depends on item B, item B depends on item C, item C depends on item A. The relationship of the items in the list conform to the relationship of the forest. d) You may assume that there would be no more than 32 items in the list depend on the same item. And the level of the dependence is less than 5.
2/2 Input The input for this problem will consist of multiple test cases. Each test case contains serval lines. A line containing a single ‘%’ signified the end of the test case. The first line of each test case contains a ‘word’ ( ‘word’ is a continuous string consists of alphabetic and digital character ) which is the game fan’s name and a integer m (0 ≤ m ≤ 1024) which is the fan’s cash. Then follows serval lines of the items in the list, each item in a seperate line. Each line contains 2 ‘words’ and 2 integers. The first ‘word’ is the name of the item. The second ‘word’ is another item it depends on. If the second ‘word’ is ‘&’, it suggests that the item doesn’t depends on any other items. The first integer is ci (0 ≤ ci ≤ 1024), the price for the item, and the second integer is hi (0 ≤ hi ≤ 100000), the pleasure the fan could get form the item. The case with the first line containing a single ‘#’ indicates the end of the input file. And this case should not be processed. Note: All the words in the input file are case-sensitive. Sample Input includes a complete case about problem. Output Output for each test begins with a line identifying the game fan’s name. The next line includes a string of ‘Max happiness:’ and an integer tells the pleasure the fan could get in the case. Then follows a line including a string of ‘Cost:’ and an integer tells the cash the fan should pay for the corresponding pleasure. Output a blank line between each case. You should not print any more whitespaces in the output. Sample Input GameFan 55 FC & 10 10 LaserGun FC 2 2 DuckHunter LaserGun 1 85 MarioBro FC 6 10 SuperMarioBro FC 6 10 SuperMarioBro2 FC 6 10 SuperMarioBro3 FC 6 10 SuperMarioBro4 FC 6 10 MD & 20 4 ShiningForceII MD 12 50 ShiningAndDarkness MD 8 40 ShiningForce MD 10 70 DemoGames MD 0 10 % # Sample Output GameFan Max happiness:231 Cost:55