Ở Hàn Quốc, sự nghịch ngợm của loài ếch nhỏ cheonggaeguri đã trở thành huyền thoại. Chúng quả thật xứng với tiếng tăm ấy: ban đêm, chúng nhảy qua ruộng lúa của bạn và làm đè bẹp các cây lúa. Sáng hôm sau, sau khi ghi lại những cây bị đè bẹp, bạn muốn xác định đường đi của con ếch gây thiệt hại nhiều nhất.

Mỗi con ếch luôn nhảy theo một đường thẳng, với khoảng cách giữa hai lần đáp liên tiếp không đổi. Các con ếch khác nhau có thể có độ dài bước nhảy và hướng nhảy khác nhau.

Các cây lúa nằm tại những giao điểm của một lưới hình chữ nhật gồm \(R\) hàng và \(C\) cột, như hình bên trái dưới đây. Mỗi con ếch nhảy xuyên qua ruộng, bắt đầu ở bên ngoài một phía và kết thúc ở bên ngoài phía bên kia, như hình bên phải.

Nhiều con ếch có thể nhảy qua ruộng. Mỗi lần đáp trong ruộng đều rơi vào một cây lúa và làm cây đó bị đè bẹp; nhiều con ếch có thể đáp xuống cùng một cây. Bạn chỉ quan sát được những cây bị đè bẹp, không nhìn thấy đường đi của các con ếch hay các lần đáp ở ngoài ruộng.

Chúng ta chỉ quan tâm đến đường đi của những con ếch đã đáp xuống ít nhất ba cây lúa trong ruộng; gọi đó là một đường đi hợp lệ. Mọi điểm đáp trong ruộng trên một đường đi như vậy đều phải là cây đã bị đè bẹp. Tuy nhiên, một cây bị đè bẹp nằm trên đường thẳng đó không nhất thiết phải là điểm đáp của con ếch đang xét. Cũng có thể có những cây bị đè bẹp không thuộc đường đi hợp lệ nào.

Hãy xác định số cây lúa lớn nhất có thể bị một con ếch đè bẹp trên một đường đi hợp lệ. Nếu không có đường đi nào thỏa mãn, kết quả là \(0\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(R,C\), với \(1\le R,C\le 5000\).
• Dòng thứ hai chứa số cây bị đè bẹp \(N\), với \(3\le N\le 5000\).
• Mỗi dòng trong \(N\) dòng tiếp theo chứa chỉ số hàng và cột của một cây bị đè bẹp. Các hàng được đánh số từ \(1\) đến \(R\), các cột từ \(1\) đến \(C\). Các vị trí này đôi một khác nhau.

Dữ liệu ra

In một số nguyên: số cây lớn nhất trên một đường đi hợp lệ, hoặc \(0\) nếu không có đường đi như vậy.

Chấm điểm

Có 25 bộ kiểm tra, mỗi bộ tương ứng 4 điểm trong thang điểm gốc 100. Một bộ kiểm tra chỉ được điểm khi kết quả đúng và chương trình chạy trong giới hạn thời gian; ngược lại được 0 điểm.

Ví dụ

6 7
14
2 1
6 6
4 2
2 5
2 6
2 7
3 4
6 1
6 2
2 3
6 3
6 4
6 5
6 7

7

6 7
18
1 1
6 2
3 5
1 5
4 7
1 2
1 4
1 6
1 7
2 1
2 3
2 6
4 2
4 4
4 5
5 4
5 5
6 6

4

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.