SP12370 TAP2012G - Generating Alien DNA

GigaFarma 是全球最大的制药公司之一，目前正在进行关于外星 DNA 的实验。其目标是生产一种具有最高商业化收益的外星 DNA 链。 所谓 _外星_ DNA 链，可以理解为由碱基序列形成的基因通过连接符连接在一起的非空序列。而每个 _基因_ 自己又是由碱基组成非空序列。并不是所有的碱基序列都能够构成有效基因，因此 GigaFarma 制定了一个外星 DNA 中会出现的基因目录，只有在这个目录中的序列才被认为是有效的。每个基因都有与其功能对应的 _价值_，而给定的外星 DNA 链的 _市场价值_ 就是组成它的基因的价值之和。 我们用小写字母 **'a'**-**'z'** 来表示不同的 _碱基_，用连字符 **'-'** 来表示 _连接符_。以下例子展示了左侧可能的基因列表及其价值，而右侧是可以通过这些基因形成的外星 DNA 链及其市场价值。 GigaFarma 只能生产称为 _可生产的_ 特定 DNA 链。这些链是由公司能合成的 DNA 片段连续组合而成，片段之间没有额外连接符。每个 _片段_ 至少含有一个连接符，但不允许存在连续、开头或结尾的连接符。每个片段都有基于生产难度的 _成本_，因此一条可生产的 DNA 链的 _生产成本_ 是组成它的片段的成本之和。下方的例子展示了左侧 DNA 片段的列表及其成本，而右侧是能够由这些片段组成的可生产 DNA 链及其生产成本。 注意，形成同一条可生产 DNA 链可能有多种不同方式。例如，**"como-como-les"** 可以通过片段 **"como-co"** 及 **"mo-les"** 以成本 **7** 形成，或直接采用片段 **"como-como-les"** 以成本 **12** 形成。在有多种合成方式时，GigaFarma 总会选择最低成本的方案。 显然，外星DNA链及可生产的DNA链的集合都是无限的。然而，GigaFarma 真正感兴趣的是它们的交集。从前面的例子中可以看到，**"como-les"** 是一条有效的外星 DNA 链，但不可生产；**"mo-les"** 是可生产的，但不是外星 DNA 链；而 **"como-como-les"** 是两者皆有。对于每一条既是外星又是可生产的 DNA 链，公司可以通过商业化获得 _净收益_，即链的市场价值减去其生产成本。当然，如果此净收益非正，则该链将不会被生产。 面对如此众多的遗传物质，GigaFarma 渴望知道从某条既可生产又是外星的 DNA 链中，能得到的最大净收益是多少。

每个测试用例由多行描述。第一行

对于每个测试用例，你需要输出一行，包含一个整数，表示 GigaFarma 能从某条既可生产又是外星的 DNA 链中获得的最大净收益。如果没有任何净收益为正，则输出 0。如果净收益可以无限大，则输出星号 **'*'**。 **本翻译由 AI 自动生成**