Cakes

The local cake shop is making a business plan for the next few months. The bakers have $C$ different recipes, each requiring its own set of ingredients and tools. Ingredients are consumed during baking, but tools are not, so a tool can be reused for other recipes. Right now the bakery has no ingredients or tools. The floods destroyed them, or the tax bureau took them away.

The son of the head chef convinced everyone to bake each type of cake only once. Internet users are reportedly willing to pay extra to be the sole owners of their own unique Nutty-Fudge Tart (NFT). The son has already estimated how much money each type of cake can earn. The bakers are now looking at each other, trying to decide which cakes to prepare for maximum profit. Given the costs of all ingredients and tools and the prices of the cakes, find the maximum profit the bakers can make.

The first line contains three integers $G$, $C$, and $T$: the number of ingredients, recipes, and tool types. The second line contains $C$ integers $c_1, \ldots, c_C$, the prices of the cakes. The third line contains $G$ integers $g_1, \ldots, g_G$, the prices of the ingredients. The fourth line contains $T$ integers $t_1, \ldots, t_T$, the prices of the tools.

The next $C$ lines each contain $G$ integers. The $j$-th integer on line $i$ is $a_{i,j}$, the amount of ingredient $j$ in cake $i$.

The last $C$ lines describe the tools. Line $i$ starts with $n_i$, the number of tools cake $i$ requires, followed by $n_i$ distinct integers $b_{i,k}$, the tools needed to prepare cake $i$.

Print a single number: the maximum profit the cake shop can make.

• $1 \leq G, C, T \leq 200$
• $0 \leq c_i, t_i \leq 10^9$
• $0 \leq g_j, a_{i,j} \leq 10^8$
• $0 \leq n_i \leq T$
• $1 \leq b_{i,k} \leq T$

The maximum profit comes from baking cakes 1 and 2 but not cake 3.