문자열 로또

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$)

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