한국에서는 청개구리들의 말썽이 가히 믿기 어려울 정도이다. 

그도 그럴 것이, 청개구리들은 여러분이 돌보고 있는 논 위를 밤사이에 마구 뛰어 다니면서 벼들을 쓰러뜨리기 때문이다

(이로 인해 농부 창호의 논도 많은 피해를 입었다고 한다). 

 

아침이 되어, 쓰러진 벼들을 파악한 당신은 가장 큰 해를 끼친 청개구리가 남긴 발자취를 파악하고 싶어 한다. 

청개구리는 논을 언제나 일직선으로 쭉 뛰어가며, 한 번에 뛰는 간격도 언제나 같다.

 

 

 

 

논은, 그림 1처럼 모눈의 교점들에 벼가 심어져 있는 구조를 하고 있다. 

그리고 문제의 청개구리들은 논 밖에서 논으로 들어와, 일직선으로 팔짝팔짝 뛰어 정확하게 벼만 짓밟고 반대편 논 밖으로 나간다. 

그림 2를 참고하라.

 

 

 

 

그림 3처럼, 여러 청개구리들이 제각기 다른 방향에서부터 논으로 들어와 서로 다른 방향으로 뛰어갈 수 있다. 

그리고 개구리에게 밟힌 벼는 쓰러진다. 여러 개구리에게 여러 번 밟히는 벼도 있다. 

하지만, 개구리들이 지나간다고 자신의 경로가 그림 3처럼 직선으로 남는 것은 아니다. 

우리가 아침이 되어 확인할 수 있는 것은 그림 4처럼, 쓰러진 벼들 뿐이다.

 

 

 

그림 4를 보면, 개구리들이 몇 마리가 와서 어느 방향으로 어느 간격으로 벼를 밟고 갔는지 그 경로를 재현할 수 있다. 

단, 벼를 세 포기 이상 밟은 개구리의 경로만 생각하기로 한다. 

그리고 이것을 개구리 경로라고 편의상 일컫겠다. 

그렇다면, 그림 4의 상황이라면 그림 3과 같은 세 개의 개구리 경로가 있다고 말할 수 있다. (물론 다른 가짓수도 있을 수 있다.)

 

한편, 첫째 칸에서 수직으로 내려가는 경로는 간격이 4인 개구리 경로일 수도 있지만, 

이 경로의 영향을 받은 벼는 두 포기밖에 없기 때문에 고려하지 않는다. 

그리고 둘째 줄 셋째 칸(2, 3), 셋째 줄 넷째 칸(3, 4), 여섯째 줄 일곱째(6, 7) 칸을 지나는 경로는 일직선이고 벼가 세 포기가 속해 있지만, 

간격이 일정하지 않기 때문에 개구리 경로로 인정하지 않는다.

 

어떤 개구리 경로에 속하는 선에는, 다른 개구리 경로에 속하는 벼가 있을 수 있다. 

예를 들어 위 그림에서 (2, 1), (2, 3), (2, 5), (2, 7)은 개구리 경로인데, 이 선 안에는 (2, 6)처럼 다른 개구리에게 밟힌 벼가 또 있다. 

그리고 사실은, 쓰러진 벼 중에는 어느 개구리 경로에도 속하지 않은 벼도 있을 수 있다. 개구리에게 밟힌 벼라고 해서,

모두 다 조건을 만족하는 '개구리 경로'에 속하는 것이 아니기 때문이다.

 

이번 문제는, 가능한 개구리 경로를 모두 조사하여, 벼를 가장 많이 밟았다고 결론지을 수 있는 개구리 경로를 찾아, 

그 경로가 지나게 되는 벼 포기의 수를 출력하는 것이다. 그림 4의 경우, 정답은 7이다.

여섯째 줄부터 가로로 벼 일곱 포기를 모두 밟는 경로가 있기 때문이다.

 

입력의 첫째 줄에는 정수 R과 C가 있다. 각각 논의 크기인 줄 수와 칸 수를 뜻한다. 1≤R, C≤5000이다. 그리고 둘째 줄에는 개구리에게 밟힌 적이 있는 벼 포기의 수 N이 있다. (3≤N≤5000) 그리고 다음 N 줄에는 밟힌 벼의 좌표인 정수 두 개가 뒤따른다. 처음 것이 줄(세로) 좌표이고 나중 것이 칸(가로) 좌표이다. (1≤줄 좌표≤R, 1≤칸 좌표≤C) 두 정수는 공백 한 칸으로 구분된다. 여러 개구리에게 밟혔더라도 벼 한 곳의 좌표는 한 번만 나온다.

가장 많은 벼를 쓰러뜨렸다고 말할 수 있는 개구리 경로가 쓰러뜨린 벼의 포깃수를 한 줄에다 출력한다. 만약 개구리 경로를 하나도 발견하지 못했다면 그냥 0을 출력한다.

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