说明

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

注意：卖出去赚到的钱不能再次用来投资。

输入格式

第一行四个数 $N,M,V,K$。

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

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

输出格式

输出一个整数，表示最多赚多少钱。

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

12

提示

数据范围及约定

对于全部数据，$N \le 60$，$M \le 240$，$V \le 1000$，$k \le 30$。