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

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

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

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