logo AlgoBeat OnlineJudge
登录 注册

#102409. [BZOJ 2409] 地下车会

内存限制:128 MiB 时间限制:30000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

地下车会设有 个分赛区, 种赛事,第 个分赛区有 场比赛。

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

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

输入格式

第一行三个数

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

接下来一行一个数 ,代表规定条数。

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

接下来一行 个数,代表

接下来 行,每行两个数

输出格式

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

样例

样例输入 #1

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

样例输出 #1

12

数据范围与提示

对于 的数据,保证 ,数据保证合法。