B. 为算法竞赛献上爆焰

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

zyx、kuro、碳钾钨 组队参加了文秦大学举办的世界巧克力包装竞赛(International Chocolate Package Contest,ICPC)。他们听说这里的人可以通过一种特殊方式学会传说中的爆焰魔法

在这里学习的部分学生,每人拥有若干帮助区间与若干学习区间。如果一个人的某个帮助区间和某个人的学习区间有交集,那么她就可以使用一些技巧,帮助对方获得爆焰魔法技能书,可以帮助自己。由于帮助别人学习爆焰魔法会使得自己受到处罚,所以每个人在自己的所有帮助区间内最多只能出手帮助一次;同理,每个人在自己的所有学习区间内最多只需被帮助一次即可学会爆焰魔法,由于学校处理不过来,所以每个时间点只会发放最多一份技能书。一旦有人在你的学习区间内帮助了你,学校会发放爆焰魔法技能书,帮你学习爆焰魔法

kuro想知道,对于最优的帮助方案,最多有多少人可以学会爆焰魔法?

形式化题意如下:

共有 个人,编号为

对每个人 ,给出:

  • 帮助区间
  • 学习区间

所有区间均为 闭区间,端点为整数。


规则说明

  1. 帮助限制

    每个人 在其所有帮助区间中, 最多只能帮助一次(可以帮助自己)

  2. 学习限制

    每个人 只要在任意一个学习区间内被帮助一次, 就能学会爆焰魔法, 不需要多次帮助

  3. 帮助发生条件

    若帮助者 的某个帮助区间 与被帮助者 的某个学习区间存在交集:

    可以选择该交集时刻帮助

  4. 系统限制

    • 每个时间点最多只会发放 一本技能书

目标

在最优安排下,求:最多有多少人可以学会爆焰魔法?

输入格式

第一行包含一个整数 ,表示人数。

接下来依次描述每个人的信息:

对于第 个人:

  • 第一行一个整数 ,表示其拥有的帮助区间数量。

  • 接下来 行,每行两个整数 ,表示一个帮助区间

  • 接下来一行一个整数 ,表示其拥有的学习区间数量。

  • 接下来 行,每行两个整数 ,表示一个学习区间

输出格式

输出一个数字,代表最多有多少人可以学会爆焰魔法。

样例

样例输入

3
2
1 3
6 7
1
9 10
1
1 1
2
5 5
8 9
0
1
2 4

样例输出

1

样例说明

  • 人 1:

    • 帮助区间:
    • 学习区间:
  • 人 2:

    • 帮助区间:
    • 学习区间:
  • 人 3:

    • 学习区间:

一种可行方案:

  • 人 1 在 无法帮助人 2 → 转而在 帮助人 3(交集为
  • 人 2 无可用帮助对象

最终共有 1 人 学会爆焰魔法。

数据范围与提示

  • 所有区间端点满足: