题目描述

给定 $3 \sim 7$ 张卡片和不超过 $4 \times 10^4$ 个合法单词，请用卡片拼出（每张卡片只能用一次）一个或多个（即“词组”）合法单词，使得用到的卡片的价值之和最大，并输出所有方案。

卡片的价值取决于卡片上的字母，其对应关系如下：

[Letter]  a b c d e f g h i j k l m n o p q r s t u v w x y z
[Value]   2 5 4 4 1 6 5 5 1 7 6 3 5 2 3 5 7 2 1 2 4 6 6 7 5 7

输入格式

第一行 $3 \sim 7$ 个小写字母，表示你手上的每张卡片都写着哪个字母。

下面不超过 $4 \times 10^4+1$ 行，每行 $3 \sim 7$ 个小写字母表示一个合法单词，以 . 作为输入结束标志。

保证所有合法单词不重复且按字典序升序给出。

输出格式

第一行输出一个整数表示最大得分。

下面若干行（按字典序升序排序），每行若干个单词（同样按字典序升序排序），表示每个最优解中拼出的单词或词组。

两个只有单词出现顺序不同的词组应算作同一个词组，此时你应该按字典序升序输出该词组中的每个单词。

prmgroa
profile
program
prom
rag
ram
rom
.

24
program
prom rag

提示

题目翻译来自NOCOW。

USACO Training Section 4.3。