3413. 新魔法药水

【题目描述】

魔法师 DD 想给 MM 送一份生日礼物，可是他没有足够的金币。魔法娴熟的 DD 自然想到了利用自己高明的魔药配制技巧来多赚一些金币。

DD 一共知道 N 种魔药（以 1..N 编号），还掌握 M 种配制魔药的方法（以 1..M 编号）。他掌握的每种配制魔药的方法都可以简单表述如下：将若干种魔药各一瓶倒入坩埚内，用魔杖搅拌的同时施出一个特定的魔法，再经过适当浓缩，就可以得到一瓶新的魔药。

森林里有一家魔法商店，这里不仅出售各种魔药，同时也以比售价略低的价格收购各种魔药。DD 的如意算盘就是：首先用自己攒下的 V 个金币去魔法商店购买一些魔药作为原料，再用一天的时间在家努力地配制，最后把配制好的成品再卖给魔法商店。

然而，由于魔法修为的原因，DD 在一天之内最多只能施出 K 次魔法。

DD 想让你帮他算一算，他最多能够在这一天时间内赚到多少金币呢？

【输入格式】

第一行有四个整数：N、M、V、K。

第二行开始的 N 行，每行有两个整数，第 i+1 行的两个整数分别表示第 i 种魔药的销售价和收购价。

第 N+2 行开始的 M 行，每行有若干个整数，表示 DD 知道的一种魔药配制方法。每行的格式都是这样的：第一个整数表示这种魔药配制方法可以得到的一瓶魔药成品的编号。下一个整数 n（n<N），表示这种配制方法需要 n 瓶原料。下面 n 个整数，表示这 n 瓶原料的编号。

【输出格式】

只需输出一个整数，表示最多可以赚到金币的数量。

【样例输入】

4 2 6 3
1 0
1 0
5 3
20 15
3 2 1 2
4 3 1 2 3

【样例输出】

12

【提示】

样例说明:一种最优方案是：买进 1 号和 2 号药水各三瓶，花费 6 金币。使用 1 号魔法 2 次，2 号魔法 1 次。最后得到一瓶 3 号药水，一瓶 4 号药水，卖得 18 金币。赚了 12 金币。

药水种类 N<=60。

配制方法数 M<=240。

初始的金币数 V<=1000。

每天可施的魔法数 K<=30。

【来源】

在此键入。