After a hard season of farming, your crops are ready to be harvested! To reward yourself for this hard work, you'd like to bake a cake — or rather — as many as you possibly can.

As you harvest each of your fields, you note down the number of items you've harvested from that field.

Given all of these harvested crops and a recipe for a cake, what is the maximum amount of cakes you can bake?

Input

The first line consists of a positive integer ~n~ ~(1 \leq n \leq 10^4)~, the number of fields you have to harvest.

The next ~n~ lines consist of ~S_i~ and ~q_i~ ~(1 \leq S_i.\text{length} \leq 10), (1 \leq q_i \leq 10^9)~ — the name of the crop harvested in the field, and the quantity of that crop harvested in that field, respectively.

The next line consists of a positive integer ~m~ ~(1 \leq m \leq 10^4)~, the number of ingredients in the cake recipe.

The next ~m~ lines consist of ~S_j~ and ~q_j~ ~(1 \leq S_j.\text{length} \leq 10), (1 \leq q_j \leq 10^9)~ — the name of an ingredient and the quantity needed for one recipe, respectively.

Output

Output a single integer, the maximum number of cakes you can make.

Clarifications

• You cannot make half-cakes or any fraction of a cake, only whole cakes.
• ~S_i~ and ~S_j~ will only consist of lowercase English characters.
• It may not always be possible to make any cakes.
• The recipe will have unique ingredients.

Example

Input 1

5
wheat 10
wheat 25
corn 5
sugar 15
tomato 100
2
wheat 1
sugar 1

Output 1

15

After harvesting all of your fields, you have a total of ~35~ wheat, ~5~ corn, ~15~ sugar, and ~100~ tomato.

The recipe for a cake consists of ~1~ wheat and ~1~ sugar, meaning you can make a maximum of ~15~ cakes. You are limited by your harvest of sugar.

Input 2

4
seed 30
grass 100
worm 10
seed 15
2
grass 20
seed 5

Output 2

5

After harvesting all of your fields, you have a total of ~45~ seed, ~100~ grass and ~10~ worm.

The recipe for a cake consists of ~20~ grass and ~5~ seed, meaning you can make a maximum of ~5~ cakes. You are limited by your harvest of grass.

Input 3

1
vanilla 6
1
chocolate 7

Output 3

0