1175: Word Chain

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：12 Solved：4

Description

Word Chain is a game similar to the idiom chain game that we often play. Now we are given a set of words and a starting letter. The task is to find the longest "chain" starting with this letter (each word can appear at most twice in the "chain"). When two words are connected, their overlapping part is combined into one part. For example, if we have the words "beast" and "astonish", and they form a chain, it becomes "beastonish". Additionally, adjacent parts of the chain cannot have a containment relationship. For example, "at" and "atide" cannot be connected.

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

The first line of input is a single integer n (n ≤ 20) representing the number of words. The following n lines each contain a single word. The last line of input is a single character representing the starting letter of the "chain". You can assume that a "chain" starting with this letter definitely exists.

Output

Only output the length of the longest "chain" starting with this letter.

Sample Input Copy 

5
at
touch
cheat
choose
tact
a

Sample Output Copy 

23

HINT

The answer of sample case is "atoucheatactactouchoose"

Source/Category