Word Groups

Interview

Time limit0.1sMemory limit1024 MB

Summary

Given N words over R letters, find the fewest letters so that every word contains at least one of the chosen letters.

Level: Medium5 of 10
Topics: Bit manipulation, Brute force, String
Solved: No attempts yet

Problem

Adam wants to build a multidimensional crossword puzzle and has picked $N$ words for it. All of the words use only the first $R$ letters of the Latin alphabet. The words can have different lengths, and the same letter can appear more than once in a word.

Adam wants to split the words into groups so that each group has at least one letter that appears in every word of that group.

Find the minimum possible number of groups.

Input

The first line contains the number of words $N$ and the number of distinct letters $R$ used in the words ( $1 \le N \le 2000$ , $2 \le R \le 15$ ). Each of the next $N$ lines contains one word. A word consists of at most 50 uppercase letters of the Latin alphabet.

Output

Print one integer: the minimum possible number of groups.

Examples2

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