재미있는 언어

단어를 이용한 잘 알려진 게임이 있습니다. 어떤 단어가 주어지면, 그 단어에 들어 있는 글자만으로 다른 단어들을 만들 수 있습니다. 이때 각 글자는 원래 단어에 등장하는 횟수만큼만 사용할 수 있으며, 글자의 순서는 상관없습니다. 예를 들어 단어 CONTEST로부터 NOTE, NET, ON, TEST, SET 등을 만들 수 있습니다.

당신은 새로운 사전을 편찬하고 있으며, 그 사전에 정확히 $n$개의 새로운 단어를 추가할 수 있습니다. 앞으로 이 게임을 하게 될 $m$개의 단어 $W_1, W_2, \ldots, W_m$을 미리 알고 있습니다. 어떤 $W_i$와도 같지 않은, 서로 다른 비어 있지 않은 단어 $n$개로 이루어진 집합 $S$를 골라서 다음 값을 최대로 만드세요.

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

여기서 $S_i \subseteq S$는 $W_i$의 글자들로 만들 수 있는, $S$에 속한 단어들의 집합입니다.

최댓값을 달성하는 집합 $S$는 여러 가지가 있을 수 있고(또한 단어의 글자 순서는 자유롭게 바꿀 수 있으므로), 단어 자체가 아니라 이 합의 최적값, 즉 만들 수 있는 단어의 최대 총 개수만 출력하세요.

첫째 줄에 두 정수 $n$과 $m$이 주어집니다 ($1 \le n \le 100$, $1 \le m \le 1000$). $n$은 추가할 수 있는 새 단어의 개수, $m$은 게임에 사용할 단어의 개수입니다. 다음 $m$개의 줄에는 각각 하나의 단어 $W_i$가 주어지며, 각 단어는 A부터 Z까지의 대문자로 이루어져 있고 길이는 최대 $100$입니다.

$\displaystyle\sum_{i=1}^{m} |S_i|$의 최댓값을 정수 하나로 출력하세요.