Funny Language

There is a well-known word game. Given a word, you may form other words using only the letters of that word, where each letter may be used at most as many times as it appears in the original word; the order of the letters does not matter. For example, from the word CONTEST you can form NOTE, NET, ON, TEST, SET, and so on.

You are compiling a new dictionary and may add exactly $n$ brand-new words to it. You already know the $m$ words $W_1, W_2, \ldots, W_m$ that you will later play this game with. Choose a set $S$ of exactly $n$ distinct non-empty words such that no chosen word equals any $W_i$, in order to maximize

$\sum_{i=1}^{m} |S_i|,$

where $S_i \subseteq S$ is the set of chosen words that can be formed from the letters of $W_i$.

Because many different sets $S$ may reach the maximum (and any word may be freely reordered), report only the optimal value of this sum — the largest total number of formable words — rather than the words themselves.

The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 1000$): the number of new words you may add and the number of game words. Each of the next $m$ lines contains one word $W_i$ consisting of at most $100$ uppercase letters from A to Z.

Print a single integer: the maximum possible value of $\displaystyle\sum_{i=1}^{m} |S_i|$.