LOSTCT - The Secret of a Lost City

no tags 

The famous archaeologist Blue Mary has found a site of a lost city. She found 12 huge steles in the center of the city - called Ice-Peak City by her, on which there were many designs. Blue Mary named these designs Ice-Peak Articles (IPA for short). Unfortunately, she can't find Ice-Peak city any more after she returns to her lab.

The only thing Blue Mary knows about Ice-Peak city is pictures of the designs on the steles. With her intelligence she soon comes up with the syntax of IPA. Its BNF form is below.

<IPA>        ::=<sentence>{<sentence>}
<sentence>   ::=<noun phrase>{<verb phrase><noun phrase>}[<verb phrase>]
<noun phrase>::=<noun>|[<adverb>]<noun phrase>
<verb phrase>::=<verb>|[<adverb>]<verb phrase>
<words>      ::=<verb>|<noun>|<adverb>

Where

nouns, verbs and adverbs are given by a dictionary which we will discuss later.

| denotes or.

Things in [] will appear zero or one time.

Things in {} will appear zero or more times.

Blue Mary has compiled a dictionary of words in IPA. Since characters appeared in IPA only contain 26 different forms, we will use small Latin letters 'a' to 'z' to represent.

There are no separators between words or sentences, so Blue Mary asks you to write a program which will split a correct IPA into minimum number of sentences, and split these sentences into minimum number of words.

Input

The first line contains the number of words in the dictionary, no more than 1000.

Next lines contain the words in the form "X.Y", one per line, where X is one of the characters 'n', 'v', 'a', denoting that the corresponding word is noun, verb or adverb, and Y is a string of lowercase Latin letters, whose length will be no more than 20.

The next line contains a correct IPA (contains only lowercase Latin letters), ends with a dot(.). The length of the IPA will be no more than 5KB.

Output

The first line contains the minimum number of sentences in IPA. The second line contains the minimum number of words in IPA, when given IPA is split into minimum number of sentences.

Example

Input:
11
n.table
n.baleine
a.silly
n.snoopy
n.sillysnoopy
v.is
v.isnot
n.kick
v.kick
a.big
v.cry
sillysnoopyisnotbigtablebaleinekicksnoopysillycry.

Output:
2
9
Time limit has been changed to 200 ms in total for all tests.


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:Chinese National Olympiad in Informatics 2000, Day 1; translated by Blue Mary and Ngo Minh Duc