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

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

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

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

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

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

第一行输入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表示是)。

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