Niềm tự hào của khu vực châu Á – Thái Bình Dương là Đại Sở thú Hình tròn vừa được xây dựng trên một hòn đảo nhỏ giữa Thái Bình Dương. Sở thú gồm các chuồng xếp thành một vòng tròn lớn, mỗi chuồng nuôi một con vật lạ.

Bạn phụ trách quan hệ công chúng của sở thú, nên nhiệm vụ của bạn là làm cho mọi người vui vẻ nhất có thể. Một xe buýt chở học sinh vừa đến, và bạn rất muốn làm các em hài lòng. Nhưng điều này không dễ: có những con vật được một số em yêu thích, lại khiến những em khác sợ hãi. Chẳng hạn, Alex thích khỉ và gấu túi vì chúng dễ thương, nhưng sợ sư tử vì hàm răng sắc nhọn. Ngược lại, Polly thích sư tử vì bộ bờm đẹp, nhưng sợ gấu túi vì chúng rất hôi.

Bạn có thể đưa một số con vật ra khỏi chuồng để các em không sợ. Tuy nhiên, nếu đưa đi quá nhiều con vật, các em sẽ chẳng còn gì để ngắm. Hãy quyết định những con vật cần đưa đi để số trẻ vui vẻ là lớn nhất.

Mỗi em đứng bên ngoài vòng tròn và nhìn thấy đúng năm chuồng liên tiếp. Bạn có danh sách các con vật mỗi em sợ và yêu thích. Một em sẽ vui vẻ nếu ít nhất một trong hai điều sau được thỏa mãn:

• Ít nhất một con vật em sợ được đưa ra khỏi tầm nhìn của em.
• Ít nhất một con vật em yêu thích vẫn ở trong tầm nhìn của em.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa hai số nguyên \(N,C\), lần lượt là số chuồng và số trẻ. Các chuồng được đánh số \(1,2,\ldots,N\) theo chiều kim đồng hồ.

Mỗi dòng trong \(C\) dòng tiếp theo mô tả một em theo dạng:

• \(E\) là chuồng đầu tiên em nhìn thấy. Em nhìn thấy các chuồng \(E,E+1,E+2,E+3,E+4\). Số hiệu vượt quá \(N\) được quay vòng về đầu; chẳng hạn, nếu \(N=14\) và \(E=13\), em nhìn thấy các chuồng \(13,14,1,2,3\).
• \(F\) là số con vật em sợ, còn \(L\) là số con vật em yêu thích.
• Các chuồng \(X_1,\ldots,X_F\) chứa những con vật em sợ.
• Các chuồng \(Y_1,\ldots,Y_L\) chứa những con vật em yêu thích.
• Các số \(X_1,\ldots,X_F,Y_1,\ldots,Y_L\) đôi một khác nhau và đều là số hiệu các chuồng em nhìn thấy.

Các em được liệt kê theo thứ tự không giảm của \(E\). Nhiều em có thể có cùng chuồng đầu tiên \(E\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số trẻ vui vẻ lớn nhất có thể đạt được.

Ràng buộc

• \(10 \le N \le 10\,000\).
• \(1 \le C \le 50\,000\).
• \(1 \le E \le N\).
• \(F,L \ge 0\) và \(F+L \le 5\).
• \(1 \le X_i,Y_j \le N\) với mọi chỉ số tương ứng hợp lệ.
• Mỗi danh sách chỉ chứa các chuồng nằm trong năm chuồng liên tiếp mà em đó nhìn thấy, và không lặp chuồng giữa hai danh sách.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm khi đúng toàn bộ test trong nhóm.

Ví dụ

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

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

6

Nguồn

APIO 2007 — Zoo.