Word Chain (Dragon)

Problem Background

Note: This is an ancient NOIP original problem; there is no guarantee that a reliable solution exists that passes all data under the given ranges.

NOIP2000, Advanced Group, Problem T3.

Problem Description

Word chain is a game similar to the idiom-chain game we often play. Now we are given a set of words and a starting letter, and we are asked to find the longest "dragon" starting with this letter (each word may appear at most twice in the "dragon"). When two words are joined, their overlapping part is merged into one part; for example, beast and astonish, if joined into a dragon, become beastonish. In addition, two adjacent parts must not have an inclusion relation; for example, at and atide cannot be joined.

Input Format

The first line of input is a single integer $n$, the number of words. The following $n$ lines each contain one word. The last line of input is a single character, the starting letter of the "dragon". You may assume that a "dragon" starting with this letter always exists.

Output Format

Output only the length of the longest "dragon" starting with this letter.

Sample Input

5
at
touch
cheat
choose
tact
a

Sample Output

23

Hint

Sample explanation: the "dragon" formed is atoucheatactactouchoose.

$n \le 20$.