Background

Special for beginners, ^_^

Description

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

Format

Input

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

Output

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

Samples

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

Limitation

前 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，

数据保证合法。