Hide

Problem I
Crafting Recipes

After months of hard work, you’ve finally finished designing a contraption for your senior capstone project. Now you just have to build it. Your design is quite complex and is composed of many parts, so you want to make sure you have enough funds to build it. You know the price of all the raw materials, and your design specifies how many parts you need to build the intermediate components. Can you determine the total price of raw materials needed to construct your contraption?

Input

The first line of input is an integer, $1 \leq N \leq 200$, specifying the number of different raw materials that make up your contraption. The following $N$ lines each contain a unique string specifying the name of a raw material, followed by an integer $1 \leq C \leq 1\, 000$ specifying the cost of a single unit of that raw material.

The next line contains an integer $1 \leq M \leq 200$ specifying the number of different intermediate components that make up the design. The following $M$ lines each contain a single “recipe” specifying the parts (where each part could be either a raw material or another intermediate component), and the quantity of each of the parts, needed to build an intermediate component. The recipe for the Capstone contraption is one of these $M$ recipes.

Each recipe begins with a string specifying the name of the intermediate component, followed by an integer $1 \leq P \leq 2\, 000$ specifying the number of different parts that make up the component. $P$ pairs of information follow: a string specifying the name of the part (which again, could be either a raw material or another intermediate component), followed by an integer $1 \leq Q \leq 1\, 000$ specifying the quantity of that part required to build the intermediate component.

You are guaranteed that all names of raw materials and intermediate components consist of only upper- and lower-case letters.

Note that there is one and only one recipe for each intermediate component, and that no intermediate component requires itself as a part in any way.

Output

The output is a single integer specifying the total cost of raw materials needed to construct the Capstone contraption.

Example

Sample Input $1$ specifies that there are two raw materials WoodenGear and MetalSprocket that have a cost of $1$ and $3$, respectively. The input also specifies two intermediate components. The Capstone component requires five StrongChassis and two WoodenGear and the StrongChassis requires three WoodenGear and five MetalSprocket. The cost of a single StrongChasis is therefore $3 \times 1 + 5 \times 3 = 18$, and the total cost of the Capstone contraption is thus $5 \times 18 + 2 \times 1 = 92$.

Sample Input 1 Sample Output 1
2
WoodenGear 1
MetalSprocket 3
2
Capstone 2 StrongChassis 5 WoodenGear 2
StrongChassis 2 WoodenGear 3 MetalSprocket 5
92
Sample Input 2 Sample Output 2
3
ConductiveHinge 4
SmoothGear 4
SleekBolt 3
3
AerodynamicGearbox 2 SleekBolt 1 SmoothGear 4
Capstone 4 StrongPlate 9 SleekBolt 3 AerodynamicGearbox 2 ConductiveHinge 5
StrongPlate 3 SmoothGear 4 SmoothGear 4 AerodynamicGearbox 5
1210

Please log in to submit a solution to this problem

Log in