Problem : 230 - Zoo

Problem Statistics

Solved Member: 8　　Submission: 46　　User Tried: 8

Statement:

新落成的環狀動物園是亞太地區之新驕傲。它座落於太平洋的小島，其造型是由不同的獸檻環繞而成的大圓環，每一獸檻內珍奇的動物皆不相同，如下圖所示。

你是動物園的公關負責人，也就是說你的工作就是要盡量的讓訪客高興。滿載著學童的巴士剛抵達，而你熱切期盼能讓他們高興。不過，這不是件容易的事。有些動物受到某些孩童喜愛，而某些動物讓有些孩童害怕。例如，小Alex 喜愛猴子和無尾熊因為它們很可愛，但因為獅子有利牙而怕它們。相反的，Polly 喜愛獅子因為它們有美麗的鬃毛，但因為無尾熊的味道而怕它們。

你可以選擇將一些獸檻內的動物移走，以避免孩童害怕。不過又擔心如果移走了太多的動物，那孩童就沒有什麼可看的了。你的任務是決定移走哪些動物以使高興的孩童越多越好。

所有的孩童都站在獸檻環的外面，每一個都可以看到相連的五個獸檻。你手上有一張清單，列出了每一個孩童喜歡的動物們及害怕的動物們。讓孩童高興的條件為：

（I)至少有一隻在他們的視線內使他們害怕的動物被移走了。或者
（II)至少有一隻在他們的視線內他們所喜愛的動物沒有被移走。

例如，考慮如下所示的孩童與動物的位置以及孩童之好惡清單：

假設你將4 號和12 號獸檻內的動物移走。這將使 Alex 和 Ka-Shu 感到高興，因為至少有一隻他們害怕的動物被移走了。這此安排仍能使Chaitanya 高興，因為他所喜愛的6號及8 號獸檻裡面的動物還在。不過Polly 和Hwan 將會不高興，因為他們沒有辦法看到任何喜愛的動物，而他們所害怕的動物卻仍然都還看得到。

考慮另外一種情形，不移走4 號及12 號獸檻裡的動物，而是移走4 號及6 號獸檻裡的動物。 Alex 和 Polly 會因此而高興因為在4 號及6 號獸檻內令他們害怕的動物被移走了。 Chaitanya 也仍會高興，因為雖然6 號獸檻內他喜愛的動物被移走了，他仍能看到8 號獸檻內他喜愛的動物。同樣的， Hwan 也會高興，因為現在可以看到12 號獸檻內他所喜愛的動物了。唯一不高興的人將會是 Ka-Shu 。

最後，考慮不移走4 號和6 號獸檻裡的動物，而只移走13 號獸檻內的動物。現在 Ka-Shu 高興了，因為他所害怕的動物被移走了，而且 Alex, Polly, Chaitanya 和 Hwan 也都高興，因為他們都至少能看到一隻喜愛的動物。因此這樣的安排會使五個孩童高興，這當然也是所有可能情形中最佳的情形。

Input:Output:

第一行的形式為N C，其中N 是獸檻的數目(10 ≤ N ≤ 10 000)，而C 是孩童的數目(1 ≤ C ≤ 50 000)。
獸檻以順時鐘方向編號為1,2,...,N。

接下來還有C 行輸入，每一行描述單一孩童的狀況。

　　每一行的形式如下：

　　E F L X1 X2 … XF Y1 Y2 … YL

其中：
　　　E是這個孩童所能看到的第一個獸檻的號碼(1 ≤ E ≤ N)。換言之，這個孩童可看到獸檻 E，E＋1，E＋2，E＋3，E+4。注意比 N 大的數字轉回來從頭開始，因此如果 N=14且E=13則這個孩童可以看到獸檻13,14,1,2,3。F是這個孩童所害怕的動物數，而 L是他所喜愛的動物的數目。獸檻號碼 X1,…,XF裡是孩童害怕的動物(1 ≤ X1,…,XF ≤ N)。獸檻號碼Y1,…,YL裡是孩童喜愛的動物 (1 ≤ Y1,…,YL ≤ N)。z 整數 X1,…,XF,Y1,…,YL內沒有任何兩數是相同的，且這些整數都是該孩童可以看到的獸檻號碼。孩童的資料將以依照其第一個可見獸檻 E 值的大小依序列出（因此 E 值最小的孩童資料會最先出現，而 E 值最大的孩童資料將最現在最後）。注意可能有超過一個孩童其第一個獸檻號碼為E。

為一整數，是所有安排中感到高興的孩童數之極大值

Sample Input:Sample Output:

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

Source:

APIO 2007

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	2000ms	16384kb
1	2000ms	16384kb	5
2	2000ms	16384kb	5
3	2000ms	16384kb	5
4	2000ms	16384kb	5
5	2000ms	16384kb	5
6	2000ms	16384kb	5
7	2000ms	16384kb	5
8	2000ms	16384kb	5
9	2000ms	16384kb	5
10	2000ms	16384kb	5
11	2000ms	16384kb	5
12	2000ms	16384kb	5
13	2000ms	16384kb	5
14	2000ms	16384kb	5
15	2000ms	16384kb	5
16	2000ms	16384kb	5
17	2000ms	16384kb	5
18	2000ms	16384kb	5
19	2000ms	16384kb	5
20	2000ms	16384kb	5