숨겨진 코드

코드 단어(code word)들의 집합과 하나의 텍스트가 주어진다. 텍스트에는 코드 단어들로 이루어진 메시지가 독특하고 때로는 모호한 방식으로 숨겨져 있다.

코드 단어와 텍스트는 모두 영문 알파벳의 대문자와 소문자로만 이루어지며, 대소문자를 구분한다. 코드 단어의 길이는 그 글자 수로 정의한다. 예를 들어 코드 단어 ALL의 길이는 $3$이다.

코드 단어의 글자들이 텍스트에서 반드시 연속으로 나타날 필요는 없다. 예를 들어 코드 단어 ALL은 언제나 A$u$L$v$L 형태의 텍스트 구간 안에 나타난다. 여기서 $u$와 $v$는 임의의(비어 있을 수도 있는) 글자열이다. 이러한 구간을 ALL에 대한 커버링 시퀀스(covering sequence)라고 부른다.

일반적으로 어떤 코드 단어에 대한 커버링 시퀀스란 다음을 모두 만족하는, 텍스트의 연속된 구간을 말한다.

• 구간의 첫 글자가 코드 단어의 첫 글자와 같다.
• 구간의 마지막 글자가 코드 단어의 마지막 글자와 같다.
• 구간에서 일부(하나도 지우지 않아도 됨) 글자를 지워 코드 단어를 만들 수 있다. 즉 코드 단어가 그 구간의 부분수열이다.

하나의 코드 단어는 텍스트 안에서 커버링 시퀀스를 여러 개 가질 수도, 하나만 가질 수도, 전혀 가지지 않을 수도 있다. 또한 하나의 커버링 시퀀스가 둘 이상의 코드 단어를 커버할 수도 있다.

커버링 시퀀스는 그 시작 위치(첫 글자의 위치)와 끝 위치(마지막 글자의 위치)로 식별한다. 텍스트의 첫 글자는 위치 $1$이다. 두 커버링 시퀀스 $c_1$, $c_2$에 대해 한쪽의 시작 위치가 다른 쪽의 끝 위치보다 (엄밀히) 크면 두 시퀀스는 겹치지 않는다고 하고, 그렇지 않으면 겹친다고 한다.

숨겨진 메시지를 뽑아내기 위해 해(solution)를 구성한다. 해란 각 항목이 하나의 코드 단어와 그 코드 단어의 커버링 시퀀스 하나를 짝지은 항목들의 집합으로, 다음 조건을 모두 만족해야 한다.

1. 선택한 커버링 시퀀스들은 서로 겹치지 않는다.
2. 선택한 각 커버링 시퀀스의 길이는 $1000$ 이하이다.
3. 선택한 코드 단어들의 길이의 총합이 최대이다. (각 항목은 자신의 코드 단어의 길이만큼 총합에 기여한다.)

• 첫째 줄에 코드 단어의 개수 $N$이 주어진다.
• 다음 $N$개의 줄에 각각 코드 단어가 하나씩 주어진다. 코드 단어는 공백 없이 이어진 글자열이며, 입력에 나타난 순서대로 $1$번부터 $N$번까지 번호가 매겨진다.
• 마지막 줄에 텍스트가 주어진다. 텍스트는 공백 없이 이어진 하나의 글자열이다.

하나의 정수를 출력한다. 모든 유효한 해에 대해 얻을 수 있는 코드 단어 길이 총합의 최댓값을 출력한다. 어떤 코드 단어도 커버링 시퀀스를 가지지 않으면 $0$을 출력한다.

• $1 \le N \le 100$. 여기서 $N$은 코드 단어의 개수이다.
• 각 코드 단어의 길이는 최대 $100$글자이다.
• 텍스트의 길이는 $1$ 이상 $1{,}000{,}000$ 이하이다.

코드 단어 $w$에 대한 커버링 시퀀스 $c$가 오른쪽 최소(right-minimal)라는 것은, $c$의 어떤 진접두(proper prefix, 즉 $c$ 자신보다 짧은 앞부분)도 $w$에 대한 커버링 시퀀스가 아님을 뜻한다. 예를 들어 코드 단어 ALL에 대해 AAALAL은 오른쪽 최소이지만, AAALALAL은 커버링 시퀀스이긴 해도 오른쪽 최소는 아니다.

주어지는 텍스트에 대해 다음이 보장된다.

1. 텍스트의 각 위치에 대해, 그 위치를 포함하는 오른쪽 최소 커버링 시퀀스의 개수는 $2500$ 이하이다.
2. 오른쪽 최소 커버링 시퀀스의 총 개수는 $10{,}000$ 이하이다.