Biologist

有一个长度为 $n$ 的 01 串，将第 $i$ 个位置取反的代价为 $v_i$。 有 $m$ 个要求，每个要求指定 $k_i$ 个位置，一种要求希望这些位置上的数都是 $0$，另一种要求希望这些个位置上的数都是 $1$。 如果满足了某个要求，你会获得 $w_i$ 的收益。一些要求是你的朋友提出的，如果你不能满足朋友提出的要求，你还需要倒贴给朋友 $g$ 元钱作为赔礼。 求你的最大收益。 $1 \le n \le 10^4, 1 \le m \le 2000, 0 \le g \le 10^4$。 ### 输入格式 第一行三个整数 $n, m, g$，表示 01 串长度，要求个数，以及不能满足朋友的要求时需要付出的赔礼。 第二行 $n$ 个数，表示初始的 01 串。 第三行 $n$ 个数，表示 $v_i$。 接下来 $m$ 行，第一个数字为 $0$ 或 $1$，表示这个要求要求每个位置上是 $0$ 还是 $1$。第二个数字 $w_i$ 表示满足这个要求你能获得的收益。第三个数字 $k_i$ 表示这个要求里对几个位置提出了要求。接下来 $k_i$ 个数分别是这些位置。最后一个数为 $0$ 或 $1$。$0$ 表示这个要求不是你的朋友提出的，$1$ 表示这个要求是你的朋友提出的。

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.

The first line contains three integers $ n $ , $ m $ , $ g $ $ (1<=n<=10^{4},0<=m<=2000,0<=g<=10^{4}) $ . 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}<=10^{4}) $ . 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}<=10^{4},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).

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

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

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

16