Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem D: PXS和小白鼠

Problem D: PXS和小白鼠

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 3
[Submit][Status][Web Board]

Description

PXS最近在进行一个可怕的研究,怎么用药物来对小白鼠进行变性。

现在有n只小白鼠,每只小白鼠变性的花费可能是不同的。第i只小白鼠的花费是vi人民币。

这种技术的变性需要一种药物,这种药物的有效期只有一天。这种实验在一天内发生,并且一天内每只小白鼠最多只能改变一次性别。

很多人都不相信PXS实现了这个技术,因此有m个人都想跟PXS打赌。如果PXS成功了,第i个人会支付PXS wi人民币。

判断PXS是否成功的方式是,对于第i个人,他会指定ki只小白鼠并指定一个性别,他认为如果这ki只小白鼠都变成了这个性别,那么PXS成功了。

如果PXS不能满足某人的条件且其不是PXS的朋友,PXS不需要付钱给他。如果PXS不能满足他的朋友提出的条件,那么PXS需要支付给这个人g人民币。

Input

第一行输入3个整数n, m, g(1<=n<=10^4, 0<=m<=2000,0<=g<=10^4)
第二行是n个整数,每个都是0或1,表示每个小白鼠的性别,0表示雌性,1表示雄性。
第三行包含n个整数,v1,v2...vn(0<=vi<=10^4)
接下来m行表示一个与PXS打赌的人。
第i行第一个数字是此人指定的性别(0或1),然后是两个整数wi,ki(0<=wi<=10^4, 1<=ki<=10)。
接下来ki个整数表示指定的小白鼠编号(1-n)。
最后一个数表示第i个人是否是PXS的好友(0表示不是,1表示是)。

Output

输出可以获得钱的最大值。(如果亏损则输出负数)。

Sample Input

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

Sample Output

2

HINT

[Submit][Status][Web Board]