Under construction

Still being built. Things may change

Cow Phrasebook

Interview

Time limit1sMemory limit1024 MB

Summary
Count how many of the N recorded messages are a prefix of at least one of the M phrases in the phrase book.
Level

Easy3 of 10

Topics
Hash map, String
Solved
No attempts yet

Problem

Farmer John loves new ideas, so he is teaching his cows to say some phrases in human language. He writes each new phrase the cows learn in his phrase book. So far the book holds M phrases (1 ≤ M ≤ 1,000).

When FJ goes on vacation, he can only reach the cows by telephone. On his trips he visits beaches and fine restaurants. When he returns, his answering machine holds N messages (1 ≤ N ≤ 10,000), and many may be from the cows.

FJ's phone service is poor, so many recorded messages are cut off before they end. Determine which messages are the beginning (prefix) of a phrase in the phrase book.

A complete phrase is 1 to 60 characters long and uses only letters (upper and lower case), periods (.), commas (,), question marks (?), and spaces. A phrase has no leading or trailing spaces and no double spaces. Comparisons are case-sensitive. A phrase counts as a prefix of itself.

Input

The first line contains two space-separated integers M and N. The next M lines each contain one phrase from the phrase book. The following N lines each contain one message spoken by a cow.

Output

Print one integer: the number of messages that are a prefix of a phrase in the phrase book.

Examples1

  1. Example 1

    Input
    3 4
I will not buy this record, it is scratched.
My hovercraft is full of eels.
Do you want to come back to my place? Bouncy, bouncy.
I will not buy this rec
My helicopter is
Do you want to come back
I will not buy this cat.
    Expected output
    2