문제

생명 공학을 연구하는 현생이는 요즘 DNA 염기서열을 연구하고 있다. DNA 염기서열이란 4종류의 핵염기 a(아데닌), c(사이토신), g(구아닌), t(티민)이 일자로 연결된 가닥이다. 문자열로는 a, c, g, t 네 문자의 나열로 나타낸다.

현생이는 인간에게 좋게 작용하는 좋은 염기서열 개를 가지고 있고 이 모든 좋은 염기서열의 길이는 이다. 주어진 좋은 염기서열은 몇 개의 와일드 카드(.)을 가지고 있어, 이 부분에는 a, c, g, t의 어떤 염기가 들어가도 좋은 염기서열로 작용한다고 하자.

주어진 좋은 염기서열의 조건을 만족할 수 있는 염기서열을 초염기서열이라고 한다. 그러나 주어진 모든 좋은 염기서열을 만족하는 것은 불가능할 수 있어서, 여러 초염기서열을 만들어서 여러 그룹의 좋은 염기서열을 커버할 수 있도록 하고자 한다.

주어진 모든 좋은 염기서열을 커버하기 위해 필요한 최소 갯수의 초염기서열은 몇 개일까?

입력

첫 번째 줄에는 좋은 염기서열의 개수과 그들의 길이 이 주어진다.

다음 개의 줄의 각 줄에는 좋은 염기서열이 주어진다.

• 주어지는 염기서열의 길이는 .
• 염기서열은 a, c, g, t, .로 이루어져 있다.

출력

첫 번째 줄에 모든 염기서열을 커버하기 위한 초염기서열의 최소 갯수를 출력한다.

서브태스크

노트

예제 1번: acgtt와 gctag의 두 가지 초염기서열을 가지고 있다면, acgtt는 a..tt와 a.g.t를 만족할 수 있고 gctag는 gc...와 .c.ag를 만족할 수 있어 모든 염기서열을 커버할 수 있다.