《算法竞赛宝典》基础算法艺术(公开课程)

【问题描述】猛兽动物园(zoo.cpp/c/pas)　APIO2007

张琪曼惊喜道：“哇，抓到这么多猛兽，把它们都关到动物园吧。不过这个牙齿锋利的狮子好可怕啊。”

楚继光：“我倒不觉得，看那头鬃毛多可爱啊，不过这大猩猩太难看了。”

　　现在这些猛兽都被关在魔法世界的圆形动物园，圆形动物园包含一大圈围栏，每个围栏里有一种动物，有K个小朋友站在大围栏圈的外面，可以看到连续的5个围栏。每个小朋友有喜欢和害怕的动物。当下面两处情况之一发生时，小朋友就会高兴： 

至少有一个他害怕的动物被移走；

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

你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你不能移走所有的动物，否则小朋友们就没有动物可看了。

例如，考虑图中的小伙伴和动物：

假如你将围栏4和12的动物移走，Alex和Ka-Shu将很高兴，因为至少有一个他们害怕的动物被移走了。这也会使Chaitanya高兴，因为他喜欢的围栏6和8中的动物都保留了。但是，Polly和Hwan将不高兴，因为他们看不到任何他们喜欢的动物，而他们害怕的动物都还在。这种安排方式使得三个小朋友高兴。 

现在，换一种方法，如果你将围栏4和6中的动物移走，Alex和Polly将很高兴，因为他们害怕的动物被移走了。Chaitanya也会高兴，虽然他喜欢的动物6被移走了，他仍可以看到围栏8里面他喜欢的动物。同样的Hwan也会因可以看到自己喜欢的动物12而高兴。唯一不高兴的只有Ka-Shu。

如果你只移走围栏13中的动物，Ka-Shu将高兴，因为有一个他害怕的动物被移走了，Alex， Polly，Chaitanya和Hwan也会高兴，因为他们都可以看到至少一个他们喜欢的动物。所以有5个小朋友会高兴。这种方法使得最多的小朋友高兴。

【输入格式】 

输入的第一行包含两个整数N，C，用空格分隔。N是围栏数(1≤N≤10 000)，C是小朋友的个数(1≤C≤50 000)。围栏按照顺时针的方向编号为1，2，3，…，N。 

接下来的C行，每行描述一个小朋友，描述下面的形式给出： E F L X₁ X₂ …X_F Y₁ Y₂ … Y_L 其中： 

E表示小朋友可以看到的第一个围栏的编号(1≤E≤N)，也就是说，小朋友可以看到的围栏为E，E+1，E+2，E+3，E+4。注意，如果编号超过N将继续从1开始算。如：当N=14，E=13时，小朋友可以看到的围栏为13，14，1，2和3。 

F表示小朋友害怕的动物数。L表示小朋友喜欢的动物数。 围栏X₁，X₂，…， X_F中包含小朋友害怕的动物。 围栏Y₁，Y₂，…， Y_L中包含该小朋友喜欢的动物。 

X₁， X₂，…，X_F， Y₁， Y₂，…Y_L是两两不同的数，而且所表示的围栏都是小朋友可以看到的。 

小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了(这样最小的E对应的小朋友排在第一个，最大的E对应的小朋友排在最后一个)。注意可能有多于一个小朋友对应的E是相同的。

【输出格式】

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

【输入样例1】

14 5 

2 1 2 4 2 6

3 1 1 6 4

6 1 2 9 6 8

8 1 1 9 12 

12 3 0 12 13 2 

【输出样例1】

6

【输入样例2】

12 7 

1 1 1 1 5 

5 1 1 5 7 

5 0 3 5 7 9 

7 1 1 7 9 

9 1 1 9 11 

9 3 0 9 11 1 

11 1 1 11 1

【输出样例2】

6

【样例说明】

第一个样例是题目描述中的例子，所有的C=5个小朋友都能高兴。第二个样例是一个不能使得所有C=7个小朋友都高兴的例子。