问题 25340 --动物园

25340: 动物园

时间限制: 1 Sec  内存限制: 128 MB
提交: 15  解决: 5
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][8476kb]

题目描述

绝恋解决问题后成为动物园的VIP*VIP,他帮助的动物园包含一大圈围栏,每个围栏里有一种富有异国风情的动物。如下图所示:

绝恋准备带着自己的MM们去动物园看动物。他希望能让她们在动物园度过一段美好的时光。但这并不是一件容易的事——有些MM喜欢某些动物,而有些MM则害怕某些动物。例如,Alex 喜欢可爱的猴子和考拉,而害怕张牙舞爪的狮子。而Polly会因狮子有美丽的鬃毛而喜欢它,但害怕有臭味的考拉。

绝恋可以选择将一些动物从围栏中移走以使得MM不会害怕。但绝恋移走的动物也不能太多,否则留给MM们观赏的动物就所剩无几了。

每个MM站在大围栏圈的外面,可以看到连续的5个围栏。绝恋得到了所有MM喜欢和害怕的动物信息。当出现下面两种情形之一时,MM就会高兴:

①至少有一个她害怕的动物(从视线可见的范围内)被移走

②至少有一个她喜欢的动物没有被(从视线可见的范围内)移走。

例如,考虑下图中的MM和动物:


MM

可见的围栏

害怕的动物

喜欢的动物

Alex

2,3,4,5,6

围栏4

围栏2,6

Polly

3,4,5,6,7

围栏6

围栏4

Chaitanya

6,7,8,9,10

围栏9

围栏6,8

Hwan

8,9,10,11,12

围栏9

围栏12

Ka-Shu

12,13,14,1,2

围栏12,13, 2

-

假如绝恋将围栏412的动物移走。AlexKa-Shu将很高兴,因为至少有一个她们害怕的动物被移走了。这也会使Chaitanya 高兴,因为她喜欢的围栏68中的动物都保留了。但是,PollyHwan将不高兴,因为她们看不到任何她们喜欢的动物,而她们害怕的动物都还在。这种安排方式使得三个MM高兴。

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

如果绝恋只移走围栏13中的动物,Ka-Shu将高兴,因为有一个她害怕的动物被移走。Alex, Polly, Chaitanya Hwan 也会高兴,因为她们都可以看到至少一个她们喜

欢的动物。所以5MM会高兴。这种方法使得最多的MM高兴。

输入

输入的第一行包含两个整数N, C,用空格分隔。N是围栏数,C MM的个数。围栏按照顺时针的方向编号为1,2,3,,N。接下来的C 行,每行描述一个MM的信息,以下面的形式给出:

E F L X1 X2 XF Y1 Y2 YL

其中:E表示这个MM可以看到的第一个围栏的编号,换句话说,该MM可以看到的围栏为E,E+1,E+2,E+3,E+4。注意,如果编号超过N 将继续从1开始算。如:当N=14, E=13时,这个MM可以看到的围栏为13,14,1,23F表示该MM害怕的动物数。L表示该MM喜欢的动物数。围栏X1,X2,,XF 中包含该MM害怕的动物。

围栏Y1, Y2, , YL 中包含该MM喜欢的动物。X1, X2, , XF, Y1, Y2, , YL 是两两不同的整数,而且所表示的围栏都是该MM可以看到的。

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


【数据范围】

10N10000

1C50000

1EN

输出

仅输出一个数,表示最多可以让多少个MM高兴。

样例输入

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

样例输出

5

提示

上面的样例1给出了前面描述的示例情形。它使得所有MMC=5)高兴.样例2给出了这样的情形,要使得所有MMC=7)都高兴是不可能的。

来源

[提交][状态]