Description

你所在的蛋糕店正在为未来几个月制定商业计划。糕点师们有 $C$ 种不同的配方，每种配方都需要各自的一套原料和工具。在烘焙过程中，原料会被消耗，而工具不会，可以被其他配方重复使用。目前，蛋糕店既没有原料，也没有工具——它们不是在最近的洪水中被毁，就是被税务局没收了。

主厨的儿子设法说服大家：每种蛋糕只做一次。网络上的人们据说愿意支付额外的费用，来成为某种独一无二的“坚果软糖挞”（Nutty-Fudge Tart，简称 NFT）的唯一拥有者。事实上，主厨的儿子已经提前估算了每种蛋糕的售价。现在，糕点师们正互相看着，思考要准备哪些蛋糕以获取最大利润。你将得到所有原料、工具的价格，以及蛋糕的售价。你的任务是确定蛋糕店能获得的最大利润。

Input Format

第一行包含三个整数 $G, C, T$，分别表示原料种类数、配方数量以及工具种类数。

第二行包含 $C$ 个用空格分隔的整数 $c_1, \ldots, c_C$，表示每种蛋糕的售价。

第三行包含 $G$ 个用空格分隔的整数 $g_1, \ldots, g_G$，表示每种原料的价格。

第四行包含 $T$ 个用空格分隔的整数 $t_1, \ldots, t_T$，表示每种工具的价格。

接下来有 $C$ 行，每行包含 $G$ 个用空格分隔的整数 $a_{i,j}$，表示制作第 $i$ 种蛋糕所需的第 $j$ 种原料数量。

最后还有 $C$ 行，每行的格式如下：第 $i$ 行以一个整数 $n_i$ 开始，表示制作第 $i$ 种蛋糕所需的工具数量。接下来是 $n_i$ 个用空格分隔的整数 $b_{i,k}$，表示制作第 $i$ 种蛋糕需要的工具编号（列出的工具互不相同）。

Output Format

输出一个整数，表示蛋糕店所能获得的最大利润。

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

Hint

注释

最大利润来自于制作蛋糕 1 和蛋糕 2，而不制作蛋糕 3。

输入限制

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

翻译由 ChatGPT-5 完成