P1149

[CTSC2007]动物园zoo

[CTSC2007]动物园zoo

新建的圆形动物园坐落在太平洋的一座小岛上，由一圈围栏组成，每个围栏中饲养一种动物。围栏按照顺时针方向编号。

今天有一群小朋友来参观动物园。每个小朋友站在围栏圈外，可以看到连续的 55 个围栏。有些动物是他喜欢的，有些动物则是他害怕的。

你可以将任意一些动物从围栏中移走，也可以移走所有动物。对于每个小朋友，如果满足以下至少一个条件，他就会感到高兴：

  • 至少有一个他害怕的动物被移走；
  • 至少有一个他喜欢的动物没有被移走。

请你选择需要移走的动物，使感到高兴的小朋友数量尽可能多，并求出这个最大数量。

输入格式

第一行包含两个整数 NN 和 CC，分别表示围栏数量和小朋友数量。

围栏按照顺时针方向编号为 1,2,3,…,N1,2,3,\ldots,N。

接下来 CC 行，每行描述一个小朋友的信息，格式如下：

E F L X1 X2 … XF Y1 Y2 … YLE\ F\ L\ X_1\ X_2\ \ldots\ X_F\ Y_1\ Y_2\ \ldots\ Y_L

其中：

  • EE 表示该小朋友能看到的第一个围栏编号。他能看到的围栏依次为 E,E+1,E+2,E+3,E+4E,E+1,E+2,E+3,E+4。编号超过 NN 后从 11 重新开始；
  • FF 表示该小朋友害怕的动物数量；
  • LL 表示该小朋友喜欢的动物数量；
  • 围栏 X1,X2,…,XFX_1,X_2,\ldots,X_F 中是该小朋友害怕的动物；
  • 围栏 Y1,Y2,…,YLY_1,Y_2,\ldots,Y_L 中是该小朋友喜欢的动物。

X1,X2,…,XF,Y1,Y2,…,YLX_1,X_2,\ldots,X_F,Y_1,Y_2,\ldots,Y_L 两两不同，并且这些围栏都在该小朋友能看到的范围内。

输入中的小朋友已经按照 EE 从小到大的顺序排列。可能有多个小朋友对应相同的 EE。

输出格式

输出一个整数，表示最多可以让多少个小朋友感到高兴。

样例输入

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

样例输出

10

数据范围

  • 10≤N≤10410\le N\le 10^4；
  • 1≤C≤5×1041\le C\le 5\times 10^4；
  • 1≤E≤N1\le E\le N。

来源与许可

本题为 CTSC 2007 试题「动物园」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

10