운이 맞는 단어

편의를 위해 A-Z 중에서 선택된 $n$개의 문자로 이루어진 긴 문자열이 주어진다. 문자열을 읽기 시작할 위치와 끝낼 위치를 임의로 정하면, 총 $\frac{n(n+1)}{2}$개의 단어를 골라낼 수 있다. 즉, 실제 스웨덴어 단어로 제한하지 않고 주어진 문자열의 어떤 부분 문자열이든 단어로 인정한다. 하지만 정해진 개수인 $v$개의 모음을 포함하는 단어에만 관심이 있다. $A, E, I, O, U, Y$를 모음으로 간주한다.

해야 할 일은 이러한 단어들 가운데 모두 서로 운이 맞는 가장 큰 그룹을 구하는 것이다. 오해를 피하기 위해, 운문을 쓰는 방식과 어느 정도 일치하기를 바라는 간단한 운의 정의를 제시한다. 두 단어가 다음 세 조건을 만족하면 서로 운이 맞는다.

• 두 단어 모두 적어도 하나의 모음을 포함해야 한다.

• 각 단어의 첫 모음부터 끝까지 두 단어가 동일해야 한다. 즉, 두 단어는 첫 모음 앞부분에서만 서로 다를 수 있다.

• 두 단어가 완전히 동일해서는 안 된다.

예를 들어 SJUNGA와 UNGA, 그리고 VARG와 KARG는 서로 운이 맞지만, VEDSTAPEL와 KONSTAPEL, DRYG와 ODRYG, TA와 TA는 서로 운이 맞지 않는다.

$ord_1$가 $ord_2$와 운이 맞고 $ord_2$가 $ord_3$와 운이 맞으면, 자동으로 $ord_1$도 $ord_3$와 운이 맞는다는 점에 유의하라.

첫째 줄에는 긴 문자열에 포함된 문자의 개수를 나타내는 정수 $1 \le 1 \le 10\,000$가 주어진다. 둘째 줄에는 만들어진 단어들이 포함해야 하는 모음의 개수를 나타내는 정수 $v$, $1 \le v \le 10$가 주어진다. 셋째 줄이자 마지막 줄에는 $n$개의 문자 $A...Z$가 공백 없이 연속해서 주어진다. 이 문자들에 포함된 모음의 개수는 항상 $v$보다 크다.

다음 조건을 만족하는 단어의 최대 개수를 나타내는 정수 하나를 출력한다.

• 문자열을 읽기 시작할 위치와 끝낼 위치를 임의로 정하여 문자 나열에서 만들 수 있고

• 정확히 $v$개의 모음을 포함하며

• 모두 서로 운이 맞는다.

단어들은 원래 문자열에서 서로 겹쳐도 되고, 원래 문자열의 같은 위치에서 시작하거나 끝나도 된다. 단, 동일한 단어를 여러 번 세어서는 안 된다는 점에 유의하라.