Bing is Chilling
Description
Bing is icecreamtarian (meaning he only eats ice cream). He needs to combine some ingredients to make his favorite ice cream flavor. He can buy each ingredient at a certain price, but he can also choose to make certain ingredients from other ingredients (which might be cheaper). Everytime Bing uses an ingredient to make another ingredient, it is consumed. Please help Bing determine the cheapest cost to make his favorite ice cream flavor.
The first line of input contains $N$ and $M$: the number of ingredients needed to make the ice cream flavor and the total number of ingredients available in the store. $(1 \leq N \leq M \leq 100,000)$
The next line contains $N$ strings separated by spaces: the names of the ingredients needed to make his favorite ice cream flavor.
Each of the next $M$ lines will be $s_i$, $p_i$, $g_i$, $[\text{ingredient names}]$: a string denoting name of the $i^{th}$ ingredient, an integer denoting the price of the $i^{th}$ ingredient, an integer denoting the number of ingredients needed to make this ingredient, followed by $g_i$ space-separated strings, the names of the ingredients needed to make this ingredient. The total character length of all $g_i$ strings across all ingredients will not exceed $3 \times 10^5$. If $g_i = 0$, the ingredient must be purchased. $(0 \leq p_i \leq 10^9, 0 \leq g_i \leq M)$
$\textbf{Note}$: it is guaranteed that all ingredients can be purchased unlimited times and have unique, single-word names consisting of alphanumeric characters.
$\textbf{Also Note}$: it is guaranteed that ingredients will not be able to make themselves either directly or their component ingredients.
Output a single integer, the minimum cost needed for Bing to make his favorite ice cream flavor (this value may not be able to fit within a standard 32-bit signed integer).
Input
The first line of input contains $N$ and $M$: the number of ingredients needed to make the ice cream flavor and the total number of ingredients available in the store. $(1 \leq N \leq M \leq 100,000)$
The next line contains $N$ strings separated by spaces: the names of the ingredients needed to make his favorite ice cream flavor.
Each of the next $M$ lines will be $s_i$, $p_i$, $g_i$, $[\text{ingredient names}]$: a string denoting name of the $i^{th}$ ingredient, an integer denoting the price of the $i^{th}$ ingredient, an integer denoting the number of ingredients needed to make this ingredient, followed by $g_i$ space-separated strings, the names of the ingredients needed to make this ingredient. The total character length of all $g_i$ strings across all ingredients will not exceed $3 \times 10^5$. If $g_i = 0$, the ingredient must be purchased. $(0 \leq p_i \leq 10^9, 0 \leq g_i \leq M)$
$\textbf{Note}$: it is guaranteed that all ingredients can be purchased unlimited times and have unique, single-word names consisting of alphanumeric characters.
$\textbf{Also Note}$: it is guaranteed that ingredients will not be able to make themselves either directly or their component ingredients.
Output
Output a single integer, the minimum cost needed for Bing to make his favorite ice cream flavor (this value may not be able to fit within a standard 32-bit signed integer).
3 5
milk vanillaExtract cream
milk 10 0
vanillaExtract 5 1 sugar
cream 30 2 sugar milk
butter 5 1 milk
sugar 6 0
1 6
flavorX2
flavorX2 100 4 skittles milk salt cream
cream 10 2 milk sugar
skittles 10 0
milk 5 0
salt 10 0
sugar 4 0
31
34