ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Regional School Programming Contest 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

K. Husband in a Shop

Time limit: 1.0 second
Memory limit: 64 MB
Mark comes home after a day of hard work. His wife, instead of feeding him, sends him to buy some bread. When Mark comes to a local shop, there is a long line of equally unhappy husbands. Mark joins the line. Fortunately, the line is moving rather quickly because each husband is asked to buy only one kind of a product.
When each husband comes to the counter, he asks for some amount of the product he needs to buy. If this amount of the product is available, he buys it and leaves the shop. If he is told that this product is unavailable, he gets terribly upset and also leaves the shop. If the available amount of the product is less than he needs, he doesn't know what to do and calls his wife for advice. In order to make a call without delaying the line, he lets one person come forward and calls his wife while standing second in line. The wife tell him to buy all the remaining products. After that he comes to the counter once again and, if the amount of the product is still the same, buys it. Otherwise, he lets one more person come forward and calls his wife again. If it happens so that the product is no longer available after a call, the customer leaves the shop empty-handed.
Mark is eager to return home and have dinner at last. Your task is to determine how many minutes will pass before he gets to the counter for the first time. Each customer spends exactly one minute at the counter and has enough time to call his wife if necessary while the following in line customer speaks to the shopgirl.

Input

The first line contains the number m of different products sold at the shop (1 ≤ m ≤ 1000). Each of the following m lines describes one product. The descriptions have the form “amount of name”, where name is the name of the product (a nonempty string of length at most 20 consisting of lowercase English letters) and amount is the amount of units of this product left by the moment Mark entered the shop (it is a positive integer not exceeding 1000). All the products have distinct names.
In the following line you are given the number n of customers standing in the line before Mark (1 ≤ n ≤ 1000). The following n lines describe the products these customers want to buy in the same format in which the products in the shop are described. There can be more than one customer who want to buy the same product. Customers may want to buy a product that is not available at the shop. The information on the customers is given in the order from the beginning of the line to its end.

Output

Output the number of minutes that Mark will stand in line before he gets to the counter for the first time.

Sample

inputoutput
3
2 of sweets
4 of milk
1 of sausage
4
2 of milk
3 of sweets
3 of milk
1 of cheese
6
Problem Author: Andrew Gein
Problem Source: Ural Regional School Programming Contest 2010
To submit the solution for this problem go to the Problem set: 1795. Husband in a Shop