Calculator Essay

It turns out that a calculator can be made to do many things it was never intended to do – one of which is to write an English essay. In this problem, you are given a list of words (each word appears at most once per occurrence in the list) which can be output by a special "calculator mode". When you press some digits on the calculator and then rotate it by \(180^\circ\), the displayed digits turn into letters. In other words, each digit corresponds to one or two letters. For example, suppose the word list contains ODD and EGG. According to the hidden mapping the calculator uses, the word ODD is produced by pressing 993 and the word EGG by pressing 000. Thus, if you arrange the words in the order ODD then EGG (forming the essay ODDEGG), you have to press 993000 on the calculator. The score of the essay is equal to the numerical value of the pressed digit sequence, that is, \(993000\).

The twist is that the calculator has a display digit limitation. In other words, if the maximum number of digits the calculator can show is \(L\), then the total length (number of digits) of your pressed sequence cannot exceed \(L\). Moreover, the calculator cannot display leading zeros. However, you are allowed to add a decimal point. For instance, if you arrange the two words in the order EGG then ODD (making the essay EGGODD), then the calculator will display the number 0.00993 (after adding the decimal point), which is a very small score.

Your task is to select some of the words (each at most once) and determine an order such that the resulting essay (formed by simply concatenating the words) can be typed on the calculator (i.e. its corresponding digit string has a length at most \(L\)) and the resulting score is maximized. Note that if there exists an arrangement whose corresponding digit string does not start with 0 then that score (an integer value) is always better than any score obtained by first having a leading zero and then adding a decimal point.

Input/Output Format: (See details below)

Mapping Details: Although the exact mapping is hidden, for the purpose of this problem you may assume that the only characters that occur in the input are from the set {O, D, E, G} and the mapping is as follows (derived from the above example):

[ \text{O} \to 9,\quad \text{D} \to 3,\quad \text{E} \to 0,\quad \text{G} \to 0. ]

Thus, ODD is converted into 993 and EGG into 000.

inputFormat

The first line contains an integer \(L\) representing the maximum number of digits that the calculator can display. The second line contains an integer \(n\) representing the number of words in the word list. Each of the following \(n\) lines contains one word (a string consisting only of the characters O, D, E, G) that can be typed on the calculator.

outputFormat

Output a single line containing the maximum possible score of the essay. The score is defined as the numerical value of the digit string obtained by converting each chosen word via the hidden mapping and concatenating them. If the concatenated digit string starts with a zero (i.e. no valid non–leading-zero integer can be formed), then a decimal point must be added in front (forming an output like 0.xxx). If no essay can be formed, output 0.

sample

6
2
ODD
EGG

993000