재미있는 언어

시간 제한1초메모리 제한128 MB

요약

주어진 m개의 단어와 겹치지 않는 n개의 새 단어를 골라, 각 단어의 글자 부분집합으로 만들어질 수 있는 경우의 합을 최대화하는 값을 구하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 조합론, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

단어를 이용한 잘 알려진 게임이 있습니다. 어떤 단어가 주어지면, 그 단어에 들어 있는 글자만으로 다른 단어들을 만들 수 있습니다. 이때 각 글자는 원래 단어에 등장하는 횟수만큼만 사용할 수 있으며, 글자의 순서는 상관없습니다. 예를 들어 단어 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|$ 의 최댓값을 정수 하나로 출력하세요.

예제7

예제 1
입력
```
3 5
A
ACM
ICPC
CONTEST
NEERC
```
예상 출력
```
8
```
예제 2
입력
```
1 1
AAA
```
예상 출력
```
1
```
예제 3
입력
```
2 1
A
```
예상 출력
```
0
```
예제 4
입력
```
5 1
AB
```
예상 출력
```
3
```
예제 5
입력
```
1 5
AB
AB
AB
A
B
```
예상 출력
```
3
```
예제 6
입력
```
4 3
AAB
ABB
ABC
```
예상 출력
```
12
```
예제 7
입력
```
6 3
AAB
ABB
ABC
```
예상 출력
```
14
```