SmallR 是一位生物学家。她最新的研究发现是如何改变狗的性别。换句话说,她可以将母狗变成公狗,反之亦然。
她将演示这项技术。现在SmallR有n只狗,每只狗的变化成本可能不同。这些狗从 1 到 n 编号。狗 i 的找零费用为 vi 元人民币。顺便说一句,这项技术需要一种只能有效一天的药物。因此实验应在一天内进行,每只狗最多可更换一次。
这一实验引起了社会各界的广泛关注。有很多富人对这个实验表示怀疑。他们都想强行跟SmallR下注。如果 SmallR 成功,第 i 个富人将向 SmallR 支付人民币。但奇怪的是他们有一种特殊的方法来判断SmallR是否成功。对于第 i 个富人,他会提前指定某些 ki 狗和某些性别。他会认为 SmallR 成功当且仅当有一天 ki 指定的狗都是指定的性别。否则,他会认为 SmallR 失败了。
如果SmallR不能满足一些不是她朋友的人,她不需要付钱给他,但如果她不能满足的人是她的好朋友,她必须付给他g人民币作为她失败的歉意。
那么,SmallR希望通过这个实验获得尽可能多的钱。请计算出 SmallR 可以获得的最大金额。顺便说一句,她有可能一分钱都得不到,甚至会赔钱。那么,请给出她应该损失的最低金额。
输入
第一行包含三个整数 n、m、g (1 ≤ n ≤ 104, 0 ≤ m ≤ 2000, 0 ≤ g ≤ 104)。第二行包含n个整数,每个是0或1,每只狗的性别,0代表雌性,1代表雄性。第三行包含 n 个整数 v1, v2, ..., vn (0 ≤ vi ≤ 104)。
接下来的 m 行每一行都描述了一个富有的人。第i行第一个数字是第i个人的指定性别(0或1),接下来的两个整数是wi和ki(0≤wi≤104,1≤ki≤10),接下来的ki个不同的整数是指定狗的索引(每个索引都在1和n之间)。该行的最后一个数字代表第 i 个人是否是 SmallR 的好朋友(0 - 否或 1 - 是)。
输出
打印一个整数,SmallR 可以获得的最大金钱。请注意,如果 SmallR 会亏损,则该整数为负数。
示例
输入 #1
5 5 9 0 1 1 1 0 1 8 6 2 3 0 7 3 3 2 1 1 1 8 1 5 1 1 0 3 2 1 4 1 0 8 3 4 2 1 0 1 7 2 4 1 1
输出 #1
2
输入 #2
5 5 8 1 0 1 1 1 6 5 4 2 8 0 6 3 2 3 4 0 0 8 3 3 2 4 0 0 0 3 3 4 1 1 0 10 3 4 3 1 1 0 4 3 3 4 1 1
输出 #2
16