新魔法药水
题目描述
商店里有 $N$ 种药水,每种药水都有一个售价和回收价。小 $S$ 攒了 $V$ 元钱,还会 $M$ 种魔法,可以把一些药水合成另一种药水。他一天可以使用 $K$ 次魔法,问他一天最多赚多少钱?
输入输出格式
输入格式
第一行四个数N、M、V、K
接下来N行,每行两个数,表示药水的售价和回收价。
接下来M行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号
输出格式
第一行四个数 $N,M,V,K$。
接下来 $N$ 行,每行两个数,表示药水的售价和回收价。
接下来 $M$ 行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号。
输入输出样例
输入样例 #1
4 2 6 3
1 0
1 0
5 3
20 15
3 2 1 2
4 3 1 2 3
输出样例 #1
12
说明
### 数据范围及约定
对于全部数据,$N \le 60$,$M \le 240$,$V \le 1000$,$k \le 30$。