Problem I
Bargainous Crafting
What’s the cheapest deal you can get on making your new pickaxe? Every item can either be crafted, purchased, or both, depending on which crafting recipes you have and depending on what’s available in the shop.
Input
At the start there is a single line containing an integer $n$ ($0 \leq n< 10^5$), the number of crafting recipes available to you, and an integer $k$, the number of items available in the shop to purchase ($1 \leq k<10^4$). The next $n$ lines each contain a recipe, starting with an integer $j$, the number of ingredients needed in the recipe, followed by a string token, the name of the craftable item, followed by $2j$ tokens, alternating between the name of a needed resource and how many instances of that resource are required in the recipe. The next $k$ lines each contain an integer $l$ ($0 \leq l \leq 2.5 \cdot 10^5$), followed by a string token, indicating you can buy the named item at the shop for price $l$. Every item’s name consists solely of lowercase English letters and underscores and is shorter than $75$ characters long.
No craftable item will directly or indirectly require itself in the given set of recipes. Pickaxes will never appear as an ingredient in any recipe.
Output
Output a single integer, the minimum number of gold pieces needed to craft a pickaxe. You are guaranteed that the result will not overflow a signed $64$-bit integer.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 5 1 pickaxe 10 steel 2 pickaxe 3 steel 1 handle 1 handle 4 oak_wood 2 steel 4 iron_ore 1 coal 3 steel 3 iron_ore 1 coal 4 oak_wood 2 steel 2 iron_ore 2 coal 150 pickaxe 45 handle 25 coal 10 iron_ore 20 oak_wood |
150 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 5 2 pickaxe 3 diamond 2 stick 1 diamond 1 iron_pickaxe 2 iron_pickaxe 3 iron 2 stick 2 iron 2 stick 1 iron_ore 1 iron_ore 1 stone_pickaxe 2 stone_pickaxe 3 stone 2 stick 1 stone 1 wood_pickaxe 1 wood_pickaxe 5 stick 1 stick 20 wood_pickaxe 50 stone 300 iron 2000 diamond |
179 |
