logo AlgoBeat OnlineJudge
登录 注册

#101711. [BZOJ 1711] [Usaco2007 Open]Dining吃饭

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

题目描述

农夫 JOHN 为牛们做了很好的食品,但是牛吃饭很挑食。每一头牛只喜欢吃一些食品和饮料而别的一概不吃。虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料。农夫 JOHN 做了 种食品并准备了 种饮料。他的 头牛都以决定了是否愿意吃某种食物和喝某种饮料。农夫 JOHN 想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料。每一件食物和饮料只能由一头牛来用。例如如果食物 被一头牛吃掉了,没有别的牛能吃食物

输入格式

  • 第一行:三个数:,和
  • 第二至 行:每一行由两个数开始 ,分别是第 头牛可以吃的食品数和可以喝的饮料数。下 个整数是第 头牛可以吃的食品号,再下面的 个整数是第 头牛可以喝的饮料号码。

输出格式

  • 第一行:一个整数,最多可以喂饱的牛数。

样例

样例输入 #1

4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3

样例输出 #1

3

样例说明

输入解释:
:食品从 ,饮料从 中选
:食品从 ,饮料从 中选
:食品从 ,饮料从 中选
:食品从 ,饮料从 中选

输出解释:
一个方案是:
Cow :不吃
Cow :食品 ,饮料
Cow :食品 ,饮料
Cow :食品 ,饮料

用鸽笼定理可以推出没有更好的解 (一共只有 种食品和饮料)。当然,别的数据会更难。

数据范围与提示

对于 的数据,。 Gold