题目描述

小 Y 喜欢速度与激情，于是他参加了地下车会。

地下车会设有 $N$ 个分赛区，$M$ 种赛事，第 $i$ 个分赛区有 $C_i$ 场比赛。

• 由于地下车会经营者想要赚到更多的钱，规定小 Y 必须参加某一些赛区的一些赛事，且第 $i$ 个分赛区至少参加 $L_i$ 场比赛。
• 小 Y 不想在一个地区逗留太久惹上麻烦，所以第 $i$ 个分赛区他最多参加 $P_i$ 场比赛。
• 可能是因为经营者对新手有歧视心理，规定了小 Y 第 $i$ 种赛事最多只能进行 $A_i$ 场比赛。

小 Y 这个月资金有点紧张，他算了算自己最多只能够维护车子跑 $K$ 场比赛。由于小 Y 是新手，所以他希望积累更多的经验，也就是跑尽可能多的赛事，现在小 Y 想知道他最多能跑多少场赛事。

输入格式

第一行三个数 $N,M,K$ 。

接下来 $N$ 行，每行第一个数为 $C_i$ ，接下来 $C_i$ 个数，代表每场比赛的种类，种类可能重复。

接下来一行一个数 $F$ ，代表规定条数。

接下来 $F$ 行，每行两个数 $A,B$ ，代表小 Y 必须参加 $A$ 赛区的 $B$ 种赛事一次及以上，一种规定只会出现一次。

接下来一行 $M$ 个数，代表$A_i$ 。

接下来 $N$ 行，每行两个数 $P_i,L_i$。

输出格式

输出一行一个数，表示小 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\le N \le 500 , 1\le M \le 500 , 1 \le L_i \le P_i \le C_i \le 500 , 1\le A_i\le 10^4, 1\le F \le 10^5 , 1\le K\le 2\times 10^5$ ，数据保证合法。