Sõnarühmad

시간 제한0.1초메모리 제한1024 MB

요약

최대 15종류의 문자로 이루어진 N개 단어를, 각 묶음마다 모든 단어에 공통으로 나타나는 문자가 하나 이상 있도록 최소 개수의 묶음으로 나눈다.

난이도: 보통10점 중 7점
유형: 비트 연산, 동적 계획법, 그리디, 조합론
정답자: 아직 제출이 없습니다

문제

Adam tahab koostada mitmemõõtmelist ristsõnamõistatust ja on selleks välja valinud $N$ sõna. On teada, et neis sõnades esinevad ainult $R$ esimest ladina tähestiku tähte. Sõnade pikkused võivad olla erinevad ja üks täht võib ühes sõnas esineda ka korduvalt.

Nüüd tahab Adam jagada need sõnad rühmadesse nii, et igas rühmas oleks vähemalt üks täht, mis esineb kõigis selle rühma sõnades.

Leia vähim võimalik rühmade arv.

입력

Sisendi esimesel real on sõnade arv $N$ ( $1 \le N \le 2\\,000$ ) ja sõnades kasutusel olevate erinevate tähtede arv $R$ ( $2 \le R \le 15$ ).

Järgmisel $N$ real on igaühel üks sõna: kuni 50 ladina tähestiku suurtähte.

출력

Väljastada üks täisarv: vähim võimalik rühmade arv, millesse need sõnad saab jagada.

예제2

예제 1
입력
```
3 4
ABC
BCD
CDA
```
예상 출력
```
1
```
예제 2
입력
```
3 3
ABA
BC
CA
```
예상 출력
```
2
```