DNA 서열 판독

의뢰인이 우주에서 온 생물의 시신을 생물 연구소에 맡기고 DNA 서열을 뽑아 달라고 요청했다. 지구 생물과 달리 이 DNA는 A, C, G, T 네 종류의 염기가 아니라 알파벳 대문자 26가지를 모두 쓴다. 그래서 DNA 서열은 모두 대문자로 된 문자열이다. 서열 분석 장치는 조직에서 DNA 서열 여러 개를 뽑아 종이에 한 줄씩 출력했다.

계약에 따르면 길이가 $M$ 이상인 서열만 유효하고, 의뢰인은 서로 다른 유효한 서열 하나마다 1달러를 준다. 연구소는 수정펜으로 종이에 출력된 각 줄의 뒤쪽에서 글자를 몇 개 지울 수 있다. 몇 개를 지울지는 줄마다 따로 정하며, 한 글자도 지우지 않아도 된다. 따라서 각 줄은 원래 출력된 서열의 접두사 중 하나가 된다.

지우는 방법을 잘 골라 종이에 남는 서로 다른 유효한 서열의 개수를 최대로 만들려고 한다. 그 최대 개수를 구하라.

입력에는 테스트 케이스가 여러 개 들어 있다. 각 테스트 케이스의 첫 줄에 두 정수 $k$와 $M$이 공백으로 구분되어 주어진다 ($1 \le k \le 500$, $1 \le M \le 500$). 이어지는 $k$개의 줄에는 정수 $n_i$와 문자열 $s_i$가 공백으로 구분되어 주어지고, 서열 $s_i$가 종이에 $n_i$줄 출력되었다는 뜻이다 ($1 \le n_i \le 500$). $s_i$는 알파벳 대문자로만 이루어지고 길이는 1 이상 500 이하다. 같은 문자열이 여러 줄에 주어질 수도 있다. 입력의 마지막 줄은 0 0이며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 만들 수 있는 서로 다른 유효한 서열의 최대 개수를 한 줄에 출력한다.