【Letter Game】

题目描述

最近流行一种字母游戏,游戏规则是这样的:每个小写英文字母有一个价值(如下图),每个单词的价值等于词中每个字母的价值之和。现在给你一个仅包含小写英文字母的多重集X和一个

单词集合A,你需要从单词集合中选出若干个单词,使得选出的单词集合中每个字母的重数之和不大于多重集中的对应字母的重数,并且使得价值最大。你只需求出这个最大价值。

多重集:允许重复元素的集合。如{a,a,b,b,b,c,c,c,c,a,a,a}

重数:每个元素出现的次数。上面多重集中 a,b,c 的重数分别为 5,3, 4 。

输入格式

输入第一行:一个字符串,即多重集中的字母。
后面若干行,每行一个字符串,表示单词集合中的一个单词,所有单词按字典顺序输入,并且无重复。输入一个”.”结尾。

输出格式

输出仅一行:选出单词组合的最大价值。

样例数据 1

输入

prmgroa
profile
program
prom
rag
ram
rom
.

输出

24

备注

【样例说明】
有两个单词集合满足条件:集合1{program} ,集合2{prom,rag}。集合1的最大价值是 24 ,集合2的最大价值也是 24(本集合两个单词的代价相加),所以最大值是 24 。

【数据范围】
|X|<=7,|A|<=40000,单词集合中每个单词的长度不超过 7 。

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*