Correcting Granny's Letter

Grandma loves to write letters, but as she has grown older, her sentences have become cluttered with extra, erroneous letters. You are given a dictionary of W words (with $1\le W\le600$), each consisting of at most 25 lowercase letters, and a sentence of L letters ($2\le L\le300$) written by Grandma. Although the sentence is supposed to be a concatenation of valid dictionary words, some extra letters have been inserted. Your task is to remove as few letters as possible so that the remaining letters (in the same order) form a valid sentence; that is, they can be segmented into one or more dictionary words.

Example: If the dictionary contains cat and tail and Grandma's sentence is catotail, then by removing the extra o you get cattail (which can be segmented as cat + tail) with only one removal.

It is guaranteed that a solution exists.

inputFormat

The first line contains an integer $W$ ($1\le W\le600$), the number of words in the dictionary. The following $W$ lines each contain a dictionary word, consisting of lowercase letters (length at most 25). The last line contains a string of $L$ ($2\le L\le300$) lowercase letters representing the sentence written by Grandma.

outputFormat

Output a single integer: the minimum number of letters that need to be removed so that the remaining letters form a valid sentence (i.e. a concatenation of one or more dictionary words).

sample

2
cat
tail
catotail

1