Codah ClubВежбај. Испрати. Напредувај.
Најави се
Македонски
#00008E

Alien Party Invites

Mr. Little Z decided to throw a party for all the aliens he had met when he was on vacation to Mars. He finally decided who is he going to invite, and has to send invitations


Mr. Little Z found a list of all the aliens he has ever met, however the names in the list are in some random order, and the list contains some names multiple times. The list is actually written on a very very long piece of paper with every name in one line. Mr. Little Z wants to cut a part of the paper from the top, and a part from the bottom such that the remaining of the list contains the names of all the people he wants to invite and the list is as short as possible


Mathematical definition: you are given a list L1 that contains K different strings and a list L2 of N strings (that can repeat). You have to find a sub-list of L2 such that it contains every element from L1 at least once.


InputThe input is read from the standard input. The first line will contain an integer N where (1 <= N <= 10000), N represents the number of aliens Mr. Little Z wants to invite to the party. Each of the next N lines contains a name of the aliens. After that, in N+2nd line there is a number M, (N <= M <= 40000) the number of aliens on the list of aliens Mr. Little Z knows. Finally the next M lines contain the names of the aliens (some names can repeat)

The list will always contain all the names of the aliens Mr. Little Z wants to invite to the party.

All the names consist of lowercase letters of the English alphabet with maximum 20 characters.

OutputYou should write to the standard input. In one and only line write one integer K representing the minimal length of the list (number of names on it) after cutting some or none parts from the top and the bottom such that the list still contains all the names of the aliens Mr. Little Z wants to invite to the party.

Examples:

Input:
3
admin
moderator
user
8
admin
moderator
hacker
programmer
user
coder
moderator
admin

Output:
4

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.