地下车会

时间限制:30s      空间限制:128MB

题目描述

小Y喜欢速度与激情,于是他参加了地下车会。  地下车会设有N 个
分赛区,M种赛事。每个分赛区有C[i]场比赛。由于地下车会经营者
想要赚到更多的钱,规定小 Y 必须参加某一些赛区的一些赛事。且
每个赛区至少参加L[i]场比赛。小Y不想在一个地区逗留太久惹上麻
烦,所以每个赛区他最多参加P[i]场比赛。可能是因为经营者对新手
有歧视心理,规定了小 Y 每种赛事最多只能进行 A[i]场比赛。小 Y
这个月资金有点紧张,他算了算自己最多只能够维护车子跑 K 场比
赛。由于小 Y 是新手,所以他希望积累更多的经验,也就是跑尽可
能多的赛事。


输入格式

第一行三个数N,M,K,用空格隔开。
接下来N行,每行第一个数C[i],接下来 C[i]个数,代表每场比赛的
种类,种类可能重复。
接下来一行一个数F,代表规定条数。
接下来 F 行,每行两个数 A,B,代表小 Y 必须参加 A 赛区的 B 种
赛事一次及以上。一种规定只会出现一次。
接下来一行M个数,代表A[i]。
接下来N行,每行两个数P[i],L[i]。


输出格式

第一行一个数ans,表示小Y最多能跑几场赛事。


样例输入

5 5 15 
5 1 1 2 2 3 
6 2 2 3 4 5 5 
3 1 2 3 
6 1 2 3 4 5 5 
4 3 3 4 4 
3 
1 2 
2 5 
5 3 
2 2 3 2 3 
4 2 
4 2 
2 1 
5 3 
3 1 

样例输出

12

提示

前 100% 的数据, 1<=N<=500 , 1<=M<=500 , 1<=C[i]<=500 ,
1<=F<=100000
【友情提示】
对于所有的数据, 1<=L[i]<=P[i]<=C[i], 1<=A[i]<=10^4, K<= 200000,
数据保证合法。 
 


题目来源

没有写明来源