Sau khi ghé thăm một bảo tàng nghệ thuật hiện đại, Farmer John quyết định thiết kế lại trang trại bằng cách di chuyển toàn bộ \(N\) (\(1 \le N \le 500\)) hàng rào giữa các đồng cỏ! Mỗi hàng rào được mô tả bởi một đoạn thẳng nằm ngang hoặc thẳng đứng trên mặt phẳng hai chiều. Nếu hai hàng rào gặp nhau thì chúng chỉ gặp tại các đầu mút.

FJ có \(C\) con bò (\(1 \le C \le 500\)) trong trang trại. Mỗi con bò ở tại một điểm trên mặt phẳng hai chiều không nằm trên bất kỳ hàng rào nào, và không có hai con bò nào ở cùng một điểm. Hai con bò được xem là thuộc cùng một cộng đồng nếu một con có thể đi đến con kia mà không chạm vào bất kỳ hàng rào nào. Hãy giúp FJ xác định số lượng bò trong cộng đồng lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(C\), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\), mô tả một hàng rào chạy từ điểm \((x_1, y_1)\) đến điểm \((x_2, y_2)\). Mỗi hàng rào hoặc thẳng đứng (\(x_1 = x_2\)) hoặc nằm ngang (\(y_1 = y_2\)). Mọi tọa độ đều nằm trong khoảng từ \(0\) đến \(1\,000\,000\).
• \(C\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\), mô tả một con bò ở vị trí \((x, y)\). Mọi tọa độ đều nằm trong khoảng từ \(0\) đến \(1\,000\,000\).

Dữ liệu ra

In ra số lượng bò trong cộng đồng lớn nhất.

Ví dụ

7 3
0 0 10 0
10 0 10 5
12 5 10 5
10 5 1 5
12 5 12 7
0 7 12 7
0 7 0 0
3 4
6 6
17 3

2

Nguồn

USACO 2012 December Contest, Bronze — Problem 3: Crazy Fences

Tác giả đề: Brian Dean, 2012.