/ StarOI / 题库 /

卫宫家今天的饭

卫宫家今天的饭

题目背景

圣诞节快到了,正义的伙伴卫宫士郎开始准备圣诞晚餐了。

圣诞节当天会有人很多来做(ceng)客(fan):藤姐,Saber,凛,樱,Rider,伊莉雅......每位客人的口味各不相同,凛想吃Archer同款蛋包饭,伊莉雅喜欢士郎做给她的烤牛肉。士郎同时还要为他们准备饮料,各人对饮料的喜好也不同。由于士郎做的菜过于好吃,所以每位客人吃到了一样自己喜欢的食物之后就会一直吃到撑,吃不下别的食物,连Saber也没办法幸免。吃的过程中也只想喝一种饮料。每一位客人会有多种喜欢的食物和饮料,同一种食物、同一种饮料也可能会被很多人喜欢,而挑剔的客人们如果看到别人的食物与饮料与自己的一样又会大(hou)打(gong)出(qi)手(huo),所以,每一种食物或者饮料只能分给一位客人,这让士郎非常头疼。为了防止冬木市恢复往日的核平,他找到同为正义的伙伴的你,让你使用对题宝具“图论算法”帮他安排一下菜单和饮料采购清单,满足尽可能多的客人。即,让尽可能多的客人同时吃到自己喜欢的食物和饮料。

输入格式

第一行三个整数,\(N\),\(F\),\(D\),表示一共有\(N\)位客(hou)人(gong)要来做(ceng)客(fan),士郎会做的食物有\(F\)种,能买到的饮料有\(D\)种。满足\(1\le N,F,D\le 100\)。

第二行至第\(N+1\)行,每行以两个整数\(f_i\)和\(d_i\)开头(\(0\le f_i \le F, 0\le d_i \le D\)),分别表示第\(i\)位客人喜欢的食物和饮料的数目,然后是\(f_i+d_i\)个整数,前\(f_i\)个整数表示第\(i\)为客人喜欢的\(f_i\)种食物,后\(d_i\)个整数表示第\(i\)位客人喜欢的\(d_i\)种饮料。

将客人擅自编号是很无礼的行为,士郎恳求你千万和他的客(hou)人(gong)们保密。

输出格式

一行,一个整数,表示士郎最多能满足的客人的数目

样例输入

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

样例输出

3

提示

士郎可以拟定如下菜谱:

  • 客人1(Lancer):莫得饭吃,莫得水喝
  • 客人2(Saber): 2号食物(荞麦面),2号饮料(肥宅快乐水)
  • 客人3(远坂凛):1号食物(蛋包饭),1号饮料(Archer特调午后红茶)
  • 客人4(伊莉雅):3号食物(士郎手制烤牛肉),3号饮料(一点点奶茶)

当然只有3种食物和3种饮料幸运E的Lancer是注定什么都吃不到的,所以士郎拿不出更好的方案了。当然并不是所有的数据都是这样的,Lancer偶尔还是能吃到点残羹剩饭的。

Limitation

2s, 128MB for each test case.

信息

难度
9
分类
(无)
标签
递交数
15
已通过
2
通过率
13%
上传者