CF311E Biologist

小 R 是一位生物学家。她最新的研究成果是如何改变狗的性别。换句话说，她可以将雌狗变成雄狗，反之亦然。 她将演示这项技术。现在小 R 有 $ n $ 只狗，每只狗改变性别的成本可能不同。狗从 1 到 $ n $ 编号。改变第 $ i $ 只狗的成本是 $ v_{i} $ 元。顺便提一下，这项技术需要一种药物，这种药物只能有效一天。因此所有实验必须在同一天内完成，每只狗最多只能改变性别一次。 这个实验引起了社会各界的广泛关注。有 $ m $ 个富人对这个实验表示怀疑。他们都想与小 R 打赌。如果小 R 成功，第 $ i $ 个富人将支付小 R $ w_{i} $ 元。但奇怪的是，他们会使用一种特殊的方法来判断 小 R 是否成功。对于第 $ i $ 个富人，他会事先指定 $ k_{i} $ 只狗和一种性别。他会认为小 R 成功当且仅当在实验后，所有指定的狗都是指定的性别。否则，他会认为小 R 失败。 如果小 R 不能满足某个不是她朋友的富人，她不需要赔偿。但如果她不能满足的是她的好朋友，她必须支付 $ g $ 元作为道歉。 然后，小 R 希望通过这个实验获得尽可能多的钱。请计算出小 R 能获得的最大金额。注意，她有可能赚不到任何钱，甚至还会亏钱。那么，请给出她最小亏损的相反数。

第一行包含三个整数 $ n,m,g$（$$1\le n\le 10^4$$，$0\le m\le 2000$，$0\le g\le 10^4$）。 第二行包含 $ n $ 个整数，每个数是 $0$ 或 $1$，表示每只狗的性别，$0$ 表示雌性，$1$ 表示雄性。 第三行包含 $ n $ 个整数 $ v_{1},v_{2},\ldots,v_{n}$（$0\le v_i\le 10^4$）。 接下来 $ m $ 行，每行描述一个富人。在第 $ i $ 行，第一个数是指定的性别（$0$ 或 $1$），接下来两个整数是 $ w_{i} $ 和 $ k_{i} $（$0\le w_{i}\le10^{4}$，$1\le k_{i}\le10$），接下来 $ k_{i} $ 个不同的整数是指定的狗的编号（每个编号在 $1$ 和 $ n $ 之间）。该行的最后一个数表示第 $i$ 个富人是否是小 R 的好朋友（$0$ — 否，$1$ — 是）。

输出一个整数，表示小 R 能获得的最大金额。注意，如果小 R 会亏钱，则该数为负。