ZOJ Problem Set - 2898
As a freshman of grave robbery, you luckily sneaked into the tomb of a great ancient emperor, and soon found the treasure room of it. After a great surprise at the valuable jewels and gold plates, you quickly recognized that it is not so easy at all: there're many traps at the door of the treasure room which were not active when you entered, but once you take a treasure up from its pedestal, some traps will be activated so you cannot leave the room safely. All the pedestals are made so meticulous that only placing an object which has exactly the same shape and the same weight with the original treasure placed on it can reset the switch and thus deactivate the traps. Of course you don't have such things. Now you begin to regret that you haven't learned how to defuse traps from your teacher, the greatest grave robber all over the world. However, you're a man with good luck and always don't give up so easily. After several attempts, you found that if either taking up treasure A or treasure B alone will activate the same trap, taking up both of them will deactivate the trap! Then it is possible for you to take away some treasures with all the traps deactivated! Maybe the ancient mechanism is not very good, or it is just a mistake of the switch designer that didn't make the traps only deactivated when all switches are off. Anyway, you're really a lucky guy. After recording the relationships between the pedestals and the traps, and then assigning a value for each treasure, you want to know the maximum value you can take from the room safely.
There're no more than 1000 test cases.
There's a blank line between consecutive test cases, processing to the end of the file.
For each test case, print the maximum value you can get in a single line.
5 2 2 3 5 3 3 2 4 5 2 3 1 2 3 4 2 1 4 10 5 1 2 3 4 5
Author: XIAO, Dong
Source: ZOJ Monthly, January 2008