AT_tenka1_2015_qualB_d 天下一電卓英作文

[problemUrl]: https://atcoder.jp/contests/tenka1-2015-qualb/tasks/tenka1_2015_qualB_d ヨシオ君は電卓を使って英作文をするのが大好きですが、イマイチ良い英作文ができません。ヨシオ君に代わって最高の英作文をしましょう。 電卓に表示した数値は、上下逆さまから見たときに英文字列とみなすことができます。例えば次のようなものです。 $ 0.7734 $  逆からみると`hELLO`  ヨシオ君はこのようにして電卓で英作文を楽しんでいます。ちなみに、ヨシオ君が使っている変換表は次のようなものです。 数字 英字 0 `O` `D` 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 $ 点が与えられる。 ### Sample Explanation 1 最高得点となる英文字列は`hELLOhELL`です。 ### Sample Explanation 2 最高得点となる英文字列は`OIOZO`です。 ### Sample Explanation 3 最高得点となる英文字列は`BEDOLDDIEshEBELDOGDIGBIG`です。 ### Sample Explanation 4 上の写真の通り小数点は電卓の表示桁数を消費しないので、桁数 $ D=5 $ の電卓で表示可能です。