단어 그룹

Adam은 다차원 십자말풀이를 만들려고 하며, 이를 위해 $N$개의 단어를 골랐다. 이 단어들은 모두 라틴 알파벳의 처음 $R$개 글자로만 이루어진다. 단어의 길이는 서로 다를 수 있고, 한 단어 안에서 같은 글자가 여러 번 나올 수도 있다.

Adam은 이 단어들을 여러 그룹으로 나누려고 한다. 각 그룹에는 그 그룹의 모든 단어에 공통으로 나오는 글자가 적어도 하나 있어야 한다.

그룹 수의 최솟값을 구하라.

첫 줄에 단어의 개수 $N$과 단어들에 쓰이는 서로 다른 글자의 개수 $R$이 주어진다 ($1 \le N \le 2000$, $2 \le R \le 15$). 다음 $N$개 줄에는 각각 한 단어가 주어진다. 단어는 최대 50자의 라틴 알파벳 대문자로 이루어진다.

분할할 수 있는 그룹 수의 최솟값을 한 줄에 출력한다.