【codecomb2092】课程选择

2014年10月13日1,2590

题目描述

大学选课总是烦恼着很多人。现在X同学选出了很多备选课,但是有的课程之间是有时间冲突的。X不会分身,自然无法在同一个时间上不同的课。每个课可能有很多备选时间,但是每个课只需要选一个时间上就可以了。当然X没有必要在不同时间上相同的课。

           现在把X的备选课及相应的上课时间告诉你,请你求出X一星期最多可以上多少课。

输入格式

第一行输入一个n,表示X将提供给你n个备选课。

接下来n行,每行包含若干个整数来描述每个备选课信息。

对于第i行,首先读入一个k,表示第i个备选课有k个时间可以选择。接下来读入k对数p,q,表示在第i个备选课在星期p的第q节课可以上。

输出格式

输出仅包含一个整数,表示X最多可以选多少节课来上。

样例数据 1

输入  [复制]

5
1 1 1
2 1 1 2 2
1 2 2
2 3 2 3 3
1 3 3

输出

4

备注

对于100%的数据:n<=300,1<=t<=84,1<=p<=7,1<=q<=12。

题解

网络流水过