문자열 로또

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

요약

길이 L인 문자열 N개가 주어질 때, 길이 K인 추첨 문자열을 골라 모든 문자열에서 부분 문자열로 나타나는 총 횟수를 최대로 만든다.

문제

DGIST 나라에는 문자열을 이용한 로또가 있다.

로또의 규칙은 아래와 같다.

구매
- 로또를 구매할 때 알파벳 대문자만으로 구성된 길이 $L$ 의 문자열을 $N$ 개 작성한다.
추첨
- 알파벳 대문자로만 구성된 길이 $K$ 의 문자열 $s$ 를 추첨한다.
- 구매 시 작성한 문자열의 모든 부분 문자열 중 $s$ 와 같은 것의 개수를 점수로 얻는다. 총점수는 구매 시 작성한 모든 문자열에 대한 점수의 총합이다.
- 여기서 부분 문자열이란, 문자열의 연속된 일부를 말한다. aek, joo, ekj는 baekjoon의 부분 문자열이고, bak, p, oone는 부분 문자열이 아니다.

달구는 이번 주에 이 로또를 하나 구매했다. 달구가 이번 주 로또 추첨에서 얻을 수 있는 총 점수의 최댓값을 구하시오.

첫 번째 줄에, 로또에 들어 있는 문자열의 길이 $L$ 과 문자열의 개수 $N$ 이 공백으로 구분되어 정수로 주어진다. ( $1 \le L \le 100$ ; $1 \le N \le 20$ )

다음 $N$ 개의 줄에 걸쳐, 달구가 이번 주에 구매한 로또에 작성한 문자열이 한 줄에 하나씩 주어진다. (주어지는 문자열은 알파벳 대문자로만 이루어져있다.)

$N+2$ 번째 줄에 정수 $K$ 가 주어진다. ( $1 \le K \le L$ )

첫 번째 줄에 달구가 이번 주 로또 추첨에서 얻을 수 있는 총 점수의 최댓값을 출력한다.