SP12370 TAP2012G - Generating Alien DNA

\[The original version of this problem (in Spanish) can be found at \] GigaFarma is one of the largest pharmaceutical companies in the world, and it is currently conducting experiments using alien DNA. Its goal is to produce a chain of alien DNA that will report the maximum possible benefit when commercialized. A chain of _alien_ DNA can be understood as a non-empty sequence of genes connected by links, and in turn each _gene_ is a non-empty sequence of bases. Because not every possible sequence of bases corresponds to a valid gene, GigaFarma has created a catalogue of genes that appear in alien DNA, which are the only ones considered valid sequences of bases. Each of these genes has a _value_ according to its functionality, and a given chain of alien DNA has a _market value_ that is the sum of the values of the genes that compose it. We will represent the different _bases_ with lowercase letters, **'a'**-**'z'**, and _links_ using a hyphen **'-'**. In the following example we can see on the left a possible list of genes and their corresponding values; on the right there are some chains of alien DNA that can be formed with these genes, along with their corresponding market values.  GigaFarma can only produce very specific DNA chains, which we call _producible_. These chains are a non-empty sequence of DNA portions that the company can synthesize, joined without any additional links between them. Each _portion_ is a sequence of bases and links containing at least one link, but without any consecutive, initial or final links. Each portion has a given _cost_, determined by the difficulty associated to its production, so each producible chain of DNA has a _production cost_ that is the sum of the costs of each of the portions that form it. In the following example, we can see on the left a list of DNA portions and their costs; on the right we have some producible chains of DNA that can be formed with these portions, along with their associated production cost.  Note that there might be multiple ways of forming the same producible chain using different portions. This is the case of **"como-como-les"** in the example, which can be obtained using portions **"como-co"** and **"mo-les"** with a production cost of **7**, or just using **"como-como-les"** with a production cost of **12**. Of course, when there is more than one way to synthesize a given producible chain of DNA, GigaFarma will always do so using the cheapest possible process. Clearly, the set of alien DNA chains is infinite, just like the set of producible DNA chains. However, GigaFarma is not directly interested in any of these sets, but in their intersection. If we check the previous examples, we can see that **"como-les"** is a valid alien DNA chain, but is not producible; **"mo-les"** is producible, but is not an alien DNA chain; and **"como-como-les"** is both. For each alien and producible DNA chain, the company can commercialize this chain to get a _net benefit_ that equals the market value of this chain minus its production cost. Of course, if this net benefit is not positive, the corresponding chain will never be produced. Because there is so much genetic material all over the place, GigaFarma would pay anything in order to know what is the maximum net benefit it can obtain for some producible and alien DNA chain.

Each test case is described using several lines. The first line

For each test case, you should print a single line containing an integer number, representing the maximum net benefit that GigaFarma can obtain from a producible and alien DNA chain. If no net benefit is positive, you should print the value 0. If the net benefit can be arbitrarily large, you should print an asteris **'\*'**.