問題文
Yoshio喜欢用计算器写英语作文,但他写不出很好的英语作文。让我们为吉雄写最好的英语作文吧。
计算器上显示的数字在倒过来看时可以看作是英文字符串。例如:
0.7734
从另一边看hELLO
这就是 Yoshio 喜欢用计算器写英语的方式。顺便说一句,Yoshio 使用的转换表如下。
| 数字 | 英字 |
|---|---|
| 0 | OD |
| 1 | I |
| 2 | Z |
| 3 | E |
| 4 | h |
| 5 | s |
| 6 | q |
| 7 | L |
| 8 | B |
| 9 | G |
根据 Yoshio 的说法,分数越高,英文字母串越好。
从其原始方向看,每个字母串的分数与计算器上显示该字符串时的数字相同。
换句话说,EGG如果 993 点、ODDEGG如果 993000 点。
另外,像普通计算器一样,最高有效数字是
您无法创建成为 0 的整数。
如果最后一个字符是O或
如果要创建像D这样的英文字符串,则需要使用小数点。
换句话说,如上图示例所示,hELLO的分数是 0.7734 点。
一方hELLOEGG如果
交换 99307734 点。
但是,根据计算器上的显示,最后一个
可以添加 0 。
可以显示
换句话说,OLD,分数为 0.7 点。
Yoshio 具有最大显示位数 D 计算器和
我有一本词汇书,其中包含 N 个单词。
单词书上的英语单词串可以在此计算器上显示的最高分数是多少?
词汇列表中包含的单词 W_1, W_2, ..., W_N 它们的编号最大为 1 选择并以任意顺序连接的英文字符串中,字符串长度为 D 找出以下分数中的最高分。
但是,您不能从词汇列表中多次选择同一个单词。
入力
输入将以以下形式通过标准输入给出。
D N W_1 W_2 : W_N
- 1 行包含一个整数,表示计算器上显示的最大位数。 给出 D ( 1 \leq D \leq 200 )。
- 2 行包含一个整数,表示词汇列表中包含的单词数。 N ( 1 \leq N \leq 10000 )。
-
3 来自行 N 行包含词汇列表中包含的单词。 W_i ( 1 \leq |W_i| \leq {\rm min}(32, D) )。
这些话是1 以每行一个字的形式给出。
W_i 是转换表中包含的字符O,D,I,Z,E,h,s,q,L,B,G'' 并且没有其他字符。 - i \neq j 如果 W_i \neq W_j 。
出力
最高分 1 行输出。
如果答案是小数,则尾随 应从输出中删除 0 。另外,小数点以下的所有内容都是 0 应作为整数输出。
在输出末尾包含换行符。 如果所有满足
配点
针对此问题设置了部分分数。 如果正确答案是满足
- N \leq 8 的测试用例都得到正确回答,45 分被给予。
- 如果所有测试用例都回答正确,除上述之外, 75 分被给予。
入力例1
9 4 hELLO hELL EGG ODD
出力例1
773407734
会给你最高分的英文字符串是hELLOhELL。
入力例2
5 3 ZO OIO IOIO
出力例2
0.201
会给你最高分的英文字符串是OIOZO。
入力例3
25 10 BED BEL BIG DIE DIG DOG OLD shE qED ZOO
出力例3
918910900738345310070038
会给你最高分的英文字符串是BEDOLDDIEshEBELDOGDIGBIG。
入力例4
5 1 hELLO
出力例4
0.7734
如上图所示,小数点不消耗计算器上显示的位数,因此位数 可以使用 D=5 计算器来显示。