题目描述

Your local cake shop is making a business plan for the next few months. The bakers have $C$ different recipes, each requiring their own set of ingredients and tools. During the baking, the ingredients are consumed, but the tools are not and can be reused for other recipes. Currently, the bakery has no ingredients or tools – they were all destroyed in the recent floods or taken away by the tax bureau.

The son of the main chef managed to convince everyone to only bake each type of cake once. Individuals on the internet are supposedly happy to pay extra to be the only owners of their own unique Nutty-Fudge Tart (NFT). In fact, the son has already gone ahead and estimated how much money they can earn for each type of cake. Now bakers are looking at each other, trying to figure out which types of cake to prepare for maximum profit. You are given the costs of all ingredients, tools, and prices of cakes. Your task is to determine how much profit the bakers can make.

输入格式

The first line contains three integers: $G$, $C$, and $T$, the number of ingredients, the number of recipes, and the number of different tools in them, respectively. The second line contains $C$ space-separated integers $c_1, \ldots, c_C$, the prices of each cake. The third line contains $G$ space-separated integers $g_1, \ldots, g_G$, representing the prices of each ingredient. The fourth line contains $T$ space-separated integers $t_1, \ldots, t_T$, representing the prices of all tools.

This is followed by $C$ lines, each containing $G$ space-separated integers $a_{i,j}$, corresponding to the amount of ingredient $j$ in cake $i$.

Finally, this is followed by $C$ lines of the following format: the $i$-th row starts with an integer $n_i$, the number of tools required for $i$-th cake. This is followed by $n_i$ space-separated integers $b_{i,k}$, indicating that we need tool $b_{i,k}$ to prepare cake $i$ (listed tools are distinct).

输出格式

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

5 3 4
14 18 21
1 2 3 1 2
5 6 3 10
0 0 1 2 0
1 2 0 1 2
5 2 1 0 0
2 1 2
2 2 3
2 3 4

3

提示

Comment

The maximum profit is made by baking cakes 1 and 2, but not cake 3.

Input limits

• $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$