/ 
Time Limit: 5 sec / Memory Limit: 256 MB
問題文
ヨシオ君は電卓を使って英作文をするのが大好きですが、イマイチ良い英作文ができません。ヨシオ君に代わって最高の英作文をしましょう。
電卓に表示した数値は、上下逆さまから見たときに英文字列とみなすことができます。例えば次のようなものです。
0.7734
逆からみるとhELLO
ヨシオ君はこのようにして電卓で英作文を楽しんでいます。ちなみに、ヨシオ君が使っている変換表は次のようなものです。
| 数字 | 英字 |
|---|---|
| 0 | OD |
| 1 | I |
| 2 | Z |
| 3 | E |
| 4 | h |
| 5 | s |
| 6 | q |
| 7 | L |
| 8 | B |
| 9 | G |
ヨシオ君によれば、得点が高いほど良い英文字列だそうです。
それぞれの英文字列の得点は、その英文字列を電卓に表示したときに、元の向きから見たときの数値と同じです。
つまり、EGGなら 993 点、ODDEGGなら 993000 点です。
また、通常の電卓と同じく、最上位桁が 0 になるような整数は作れません。
最後の文字がOかDであるような英文字列を作りたい場合は小数点を利用する必要があります。
つまり、上の写真の例の通り、hELLOの得点は 0.7734 点となります。
一方hELLOEGGであれば 99307734 点です。
ただし、電卓の表示としては、末尾の 0 は付けても良いものとします。
つまり、OLDという表示は可能であり、その得点は 0.7 点となります。
ヨシオ君は最大表示桁数 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 行につき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 の電卓で表示可能です。