Problem E
Benchmaking
After a day of gathering resources, it is time for Steve, Alex, and Kai to build their base and equip themselves with better gear. They have made a list of the items they need, but they’re not yet sure whether they have all the raw materials required.
They know a set of recipes, each allowing them to convert a set of materials into another material or item. Creating an item requires several steps. For example, crafting a new iron pickaxe requires converting logs into planks, then planks into sticks, and iron ore into iron ingots. At that point, the sticks and ingots can be connected to make an iron pickaxe.
Given the list of items they need and the set of recipes that they know, can you output an exact list of the raw materials that they need? A material is considered raw if there is not a recipe that produces it. In the above example, the raw materials are logs and iron ore.
Input
Input begins with a single integer, $r$, the number of recipes that they know ( $1 \le r < 10^4 $ ). The next part of the input details each of the $r$ recipes. To improve readability of the input file, recipes are delimited by a line with five hyphens. This delimiter is included before and after the recipe section and between pairs of recipes.
Note that the set of recipes is acyclic — no item can be crafted into something else that can be used to craft the original item again.
Each recipe begins with a line stating its output: an integer $c_o$ and a string $s_o$, indicating that the recipe produces $c_o$ units of item $s_o$. You are given that $1 \le c_o \le 16$, and all values of $s_o$ are unique (there is only one recipe to create each given product).
The next line has an integer $q$ ($1 \le q \le 9$), the number of distinct materials this recipe requires as input.
The next $q$ lines describe the materials needed for this recipe. Each line has an integer, $c_i$, and a string, $s_i$, indicating that $c_i$ of item $s_i$ are required for this recipe ($1 \le c_i \le 9$).
After the recipe section, the final section begins with an integer, $n$ ($1 \le n \le 10^4$), the number of distinct items they need for their gear and base.
The next $n$ lines each contain two values, an integer $c_f$ and a string $s_f$, indicating that they need $c_f$ of item $s_f$ ($1 \le c_f \le 10^9$).
All item and material names consist of lowercase letters and underscores, and are between 1 and 15 characters long. The number of distinct item/material names in the input will not exceed $10^4$.
Output
For each raw material they need, output a line containing two values, the required quantity (an integer) and the name of the resource (a string). The raw materials may be output in any order.
It is guaranteed that the required amount of any single raw or intermediate resource does not exceed $10^9$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 ----- 1 crafting_table 1 4 oak_plank ----- 4 oak_plank 1 1 oak_log ----- 1 1 crafting_table |
1 oak_log |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 ----- 1 iron_pickaxe 2 2 stick 3 iron_ingot ----- 1 iron_sword 2 2 iron_ingot 1 stick ----- 4 stick 1 2 oak_plank ----- 4 oak_plank 1 1 oak_log ----- 1 iron_helmet 1 5 iron_ingot ----- 1 iron_ingot 1 1 iron_ore ----- 4 3 iron_sword 3 saddle 3 iron_pickaxe 3 iron_helmet |
30 iron_ore 2 oak_log 3 saddle |