Problem Description

Yoshio loves composing English sentences using a calculator, but he hasn't been able to create good ones. Let's help Yoshio create the best English sentence.

The numbers displayed on the calculator can be interpreted as English letters when viewed upside down. For example:

$ 0.7734 $

When viewed upside down, it becomes hELLO

Yoshio enjoys composing English sentences this way on his calculator. The conversion table he uses is as follows:

According to Yoshio, the higher the score, the better the English string. The score of each English string is the same as the number displayed on the calculator when viewed from the original direction.

For example, EGG scores $ 993 $ points, and ODDEGG scores $ 993000 $ points.

Similarly, as with a regular calculator, integers cannot have leading zeros. If the last character of the string is O or D, a decimal point must be used. For instance, as shown in the photo above, the score for hELLO is $ 0.7734 $ points. On the other hand, hELLOEGG scores $ 99307734 $ points.

However, as a display on the calculator, trailing zeros are acceptable. Thus, the display OLD is possible, and its score is $ 0.7 $ points.

Yoshio has a calculator with a maximum display digit count of $ D $ and a dictionary with $ N $ words. What is the highest score of an English string that can be displayed on this calculator, composed of words from the dictionary?

From the dictionary containing words $ W_1, W_2, ..., W_N $, select one or more words and concatenate them in any order to form an English string with a length of $ D $ or less. Find the highest score among these strings. Note that the same word cannot be chosen multiple times.

Input Format

The input is given from the standard input in the following format:

$ D $ $ N $ $ W_1 $ $ W_2 $ : $ W_N $

• The first line contains an integer $ D $ ( $1 \leq D \leq 200$ ), representing the maximum display digits of the calculator.
• The second line contains an integer $ N $ ( $1 \leq N \leq 10000$ ), representing the number of words in the dictionary.
• The next $ N $ lines contain the words $ W_i $ ( $1 \leq |W_i| \leq \min(32, D)$ ) from the dictionary, one word per line.
  These words consist only of the characters O, D, I, Z, E, h, s, q, L, B, G and do not contain any other characters.
• $W_i \neq W_j$ for $i \neq j$.

Output Format

Output the highest score in one line.

If the answer is a decimal, remove trailing zeros. If the decimal part is all zeros, output it as an integer.

End the output with a newline.

Sample Input and Output

Sample Input #1

9
4
hELLO
hELL
EGG
ODD

Sample Output #1

773407734

Sample Input #2

5
3
ZO
OIO
IOIO

Sample Output #2

0.201

Sample Input #3

25
10
BED
BEL
BIG
DIE
DIG
DOG
OLD
shE
qED
ZOO

Sample Output #3

918910900738345310070038

Sample Input #4

5
1
hELLO

Sample Output #4

0.7734

Notes/Hints

Scoring

This problem has partial points.

• If you correctly solve all test cases where $N \leq 8$, you will be awarded $ 45 $ points.
• If you correctly solve all test cases, you will be awarded an additional $ 75 $ points.

Sample Explanation 1

The English string with the highest score is hELLOhELL.

Sample Explanation 2

The English string with the highest score is OIOZO.

Sample Explanation 3

The English string with the highest score is BEDOLDDIEshEBELDOGDIGBIG.

Sample Explanation 4

As shown in the photo, the decimal point does not consume the display digits of the calculator, so it is possible to display it on a calculator with $ D=5 $ digits.

见题面 Input 部分

见题面 Output 部分