P2549 Calculator Writes an Essay

As we all know, a calculator can be used for many things it was not meant to do, like playing music. Xiao A discovered a hidden feature of a calculator — writing English essays. He presses some digits on the calculator, and after rotating the display by $180$ degrees, it becomes the essay. Each digit corresponds to one or two letters.  Xiao A prepared a word list, chooses some words from it, and arranges them in an order to form an essay. This essay can be typed on the calculator. For example, if the word list contains `ODD` and `EGG`, and the essay is `ODDEGG`, then you need to press `993000` on the calculator, and the score of this essay is $993000$. Words in the list cannot be reused. If the list contains multiple identical words, each occurrence can be used at most once. Words cannot be split. Xiao A wants the essay to have the highest possible score. Of course, the calculator has a digit limit, so the essay length cannot exceed the number of display digits. The calculator cannot display leading zeros, but you may insert a decimal point. For example, if the essay is `EGGODD`, you have to type $0.00993$, which is the score of the essay, though that score is too small.

The first line contains $D$, the number of display digits of the calculator. The second line contains $N$, the number of words. The next $N$ lines each contain one word, guaranteed to be convertible to digits.

Output one line containing the maximum score.

For $40\%$ of the testdata, $D \leq 20, N \leq 10$. For $100\%$ of the testdata, $D \leq 200, N \leq 10000$, and the word length $\leq 32$. Translated by ChatGPT 5