CF311E.Biologist

SmallR is a biologist. Her latest research finding is how to change the sex of dogs. In other words, she can change female dogs into male dogs and vice versa.

She is going to demonstrate this technique. Now SmallR has n dogs, the costs of each dog's change may be different. The dogs are numbered from 1 to n. The cost of change for dog i is v__i RMB. By the way, this technique needs a kind of medicine which can be valid for only one day. So the experiment should be taken in one day and each dog can be changed at most once.

This experiment has aroused extensive attention from all sectors of society. There are m rich folks which are suspicious of this experiment. They all want to bet with SmallR forcibly. If SmallR succeeds, the i-th rich folk will pay SmallR w__i RMB. But it's strange that they have a special method to determine whether SmallR succeeds. For i-th rich folk, in advance, he will appoint certain k__i dogs and certain one gender. He will think SmallR succeeds if and only if on some day the k__i appointed dogs are all of the appointed gender. Otherwise, he will think SmallR fails.

If SmallR can't satisfy some folk that isn't her friend, she need not pay him, but if someone she can't satisfy is her good friend, she must pay g RMB to him as apologies for her fail.

Then, SmallR hope to acquire money as much as possible by this experiment. Please figure out the maximum money SmallR can acquire. By the way, it is possible that she can't obtain any money, even will lose money. Then, please give out the minimum money she should lose.

SmallR 是一位生物学家。她最新的研究发现是如何改变狗的性别。换言之，她可以将母狗变为公狗，也可以将公狗变为母狗。

她即将演示这项技术。目前，SmallR 拥有 $n$ 只狗，每只狗的变性成本可能各不相同。这些狗编号为 $1$ 到 $n$。对第 $i$ 只狗进行变性的成本为 $v_i$ 元人民币。顺便提一下，该技术需要一种仅在一天内有效的药物。因此，整个实验必须在一天内完成，且每只狗最多只能变性一次。

该实验已引起社会各界的广泛关注。共有 $m$ 位富人对此实验表示怀疑，他们均强行要求与 SmallR 打赌。若 SmallR 实验成功，第 $i$ 位富人将向 SmallR 支付 $w_i$ 元人民币。但奇怪的是，他们采用一种特殊方式来判定 SmallR 是否成功：对第 $i$ 位富人而言，他事先会指定某 $k_i$ 只狗以及某一特定性别；当且仅当在某一天这 $k_i$ 只被指定的狗全部为所指定的性别时，他才认为 SmallR 成功；否则，他认为 SmallR 失败。

若 SmallR 无法满足某位并非她朋友的富人，她无需向其支付任何费用；但若她无法满足某位她的好友，则必须向其赔偿 $g$ 元人民币作为歉意。

SmallR 希望通过该实验尽可能多地获取收益。请计算出她所能获得的最大收益。顺便说明，她也可能无法获得任何收益，甚至可能亏损。此时，请给出她最少需要亏损的金额。

The first line contains three integers n, m, g (1 ≤ n ≤ 104, 0 ≤ m ≤ 2000, 0 ≤ g ≤ 104). The second line contains n integers, each is 0 or 1, the sex of each dog, 0 represent the female and 1 represent the male. The third line contains n integers _v_1, _v_2, ..., v__n (0 ≤ v__i ≤ 104).

Each of the next m lines describes a rich folk. On the i-th line the first number is the appointed sex of i-th folk (0 or 1), the next two integers are w__i and k__i (0 ≤ w__i ≤ 104, 1 ≤ k__i ≤ 10), next k__i distinct integers are the indexes of appointed dogs (each index is between 1 and n). The last number of this line represents whether i-th folk is SmallR's good friend (0 — no or 1 — yes).

第一行包含三个整数 $n$、$m$、$g$（$1 \leq n \leq 10^4$，$0 \leq m \leq 2000$，$0 \leq g \leq 10^4$）。
第二行包含 $n$ 个整数，每个为 $0$ 或 $1$，表示每只狗的性别：$0$ 表示雌性，$1$ 表示雄性。
第三行包含 $n$ 个整数 $v_1,\,v_2,\,\dots,\,v_n$（$0 \leq v_i \leq 10^4$）。

接下来的 $m$ 行描述了 $m$ 位富人。第 $i$ 行中，第一个数为第 $i$ 位富人指定的性别（$0$ 或 $1$），随后两个整数为 $w_i$ 和 $k_i$（$0 \leq w_i \leq 10^4$，$1 \leq k_i \leq 10$），接着是 $k_i$ 个互不相同的整数，表示被指定的狗的编号（每个编号在 $1$ 到 $n$ 之间）。该行最后一个数表示第 $i$ 位富人是否为 SmallR 的好朋友（$0$ 表示否，$1$ 表示是）。

Print a single integer, the maximum money SmallR can gain. Note that the integer is negative if SmallR will lose money.

输出一个整数，表示 SmallR 能获得的最大金额。注意：若 SmallR 将亏损，则该整数为负数。