Word Grouping

Time limit1sMemory limit1024 MB

Summary

Split N words into the fewest groups so that each group shares at least one common letter, with at most 15 distinct letters.

Level: Medium6 of 10
Topics: Bit manipulation, Dynamic programming, Greedy
Solved: No attempts yet

Problem

Adomas has decided to build a multidimensional crossword, and to do so he needs to split his words into groups.

He has chosen $N$ words. The words use only the first $R$ letters of the Latin alphabet. The same letter may appear several times within a word, and the words may have different lengths.

Adomas wants to split all of the words into as few groups as possible so that every group has at least one letter that is shared by all of the words in that group.

Determine the minimum number of groups into which the words can be split.

Input

The first line contains the number of words $N$ and the number of distinct letters $R$ used in the words. Each of the next $N$ lines contains one word — a string of at most 50 uppercase Latin letters that uses only the first $R$ letters of the alphabet.

Output

Output the minimum number of groups into which the words can be split.

Constraints

$1 \le N \le 2000$
$2 \le R \le 15$

Examples2

Example 1
Input
```
3 4
ABC
BCD
CDA
```
Expected output
```
1
```
Example 2
Input
```
3 3
ABA
BC
CA
```
Expected output
```
2
```