Hidden Codes

You are given a set of code words and a text. The text hides a message assembled from the code words, embedded in a peculiar (and possibly ambiguous) way.

Both the code words and the text consist only of upper- and lower-case letters of the English alphabet, and matching is case-sensitive. The length of a code word is its number of letters (for example, the code word ALL has length $3$).

The letters of a code word need not appear consecutively in the text. For instance, the code word ALL always appears inside a stretch of the text of the form A$u$L$v$L, where $u$ and $v$ are arbitrary (possibly empty) runs of letters. Such a stretch is called a covering sequence for ALL.

In general, a covering sequence for a code word is a contiguous stretch of the text such that:

• its first letter equals the first letter of the code word,
• its last letter equals the last letter of the code word, and
• the code word can be obtained from it by deleting some (possibly none) of its letters (that is, the code word is a subsequence of the stretch).

A code word may have one, many, or no covering sequences in the text, and a single covering sequence may cover more than one code word.

A covering sequence is identified by its start position (the position of its first letter) and its end position (the position of its last letter); the first letter of the text is at position $1$. Two covering sequences $c_1$ and $c_2$ do not overlap if the start position of one is strictly greater than the end position of the other; otherwise they overlap.

To extract the hidden message you build a solution: a set of items, each pairing a code word with one of its covering sequences, so that:

1. the chosen covering sequences are pairwise non-overlapping;
2. every chosen covering sequence has length at most $1000$;
3. the total length of the chosen code words is as large as possible (each item contributes the length of its code word).

• The first line contains the integer $N$, the number of code words.
• Each of the next $N$ lines contains one code word: a run of letters with no spaces. The code words are numbered $1$ through $N$ in the order they appear.
• The last line contains the text: a single run of letters with no spaces.

Print a single integer: the maximum achievable total, i.e. the largest possible sum of the lengths of the code words over all valid solutions. If no code word has a covering sequence, print $0$.

• $1 \le N \le 100$, where $N$ is the number of code words.
• Each code word has length at most $100$ letters.
• The length of the text is between $1$ and $1{,}000{,}000$ letters (inclusive).

Call a covering sequence $c$ for a code word $w$ right-minimal if no proper prefix of $c$ (an initial part of $c$ shorter than $c$ itself) is also a covering sequence for $w$. For example, for the code word ALL, the stretch AAALAL is right-minimal, whereas AAALALAL is a covering sequence but is not right-minimal.

For the given text it is guaranteed that:

1. for every position of the text, the number of right-minimal covering sequences containing that position is at most $2500$;
2. the total number of right-minimal covering sequences is at most $10{,}000$.