题目描述

商店里有N种药水，每种药水都有一个售价和回收价。小S攒了V元钱，还会M种魔法，可以把一些药水合成另一种药水。他一天可以使用K次魔法，问他一天最多赚多少钱？

输入格式

第一行四个数N、M、V、K

接下来N行，每行两个数，表示药水的售价和回收价。

接下来M行，每行若干个数，第一个数表示魔法的成品，第二个数是原料的种数，接下来为各种原料的编号

输出格式

一个数，表示小S的最大利润

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

12

提示

N<=60 M<=240

V<=1000

k<=30