프로그램 명: ioi_frog
제한시간: 2 초
한국에서는 청개구리들이 부리는 말썽이 가히 믿기 어려울 정도이다. 그도 그럴 것이, 청개구리들은 여러분이 돌보고 있는 논 위를 밤 사이에 마구 뛰어 다니면서 벼들을 쓰러뜨리기 때문이다. 아침이 되어, 쓰러진 벼들을 파악한 당신은 가장 큰 해를 끼친 청개구리가 남긴 발자취를 파악하고 싶어한다. 청개구리는 논을 언제나 일직선으로 쭉 뛰어가며, 한 번에 뛰는 간격도 언제나 같다.

논은, 그림 1처럼 모눈의 교점들에 벼가 심어져 있는 구조를 하고 있다. 그리고 문제의 청개구리들은 논 밖에서 논으로 들어와, 일직선으로 팔짝팔짝 뛰어 정확하게 벼만 짓밟고 반대편 논 밖으로 나간다. 그림 2를 참고하라.

그림 3처럼, 여러 청개구리들이 제각기 다른 방향에서부터 논으로 들어와 서로 다른 방향으로 뛰어갈 수 있다. 그리고 개구리에게 밟힌 벼는 쓰러진다. 여러 개구리에게 여러 번 밟히는 벼도 있다. 하지만, 개구리들이 지나간다고 자신의 경로가 그림 3처럼 직선으로 남는 것은 아니다. 우리가 아침이 되어 확인할 수 있는 것은 그림 4처럼, 쓰러진 벼들 뿐이다.

그림 4를 보면, 개구리들이 몇 마리가 와서 어느 방향으로 어느 간격으로 벼를 밟고 갔는지 그 경로를 재현할 수 있다. 단, 벼를 세 포기 이상 밟은 개구리의 경로만 생각하기로 한다. 그리고 이것을 개구리 경로라고 편의상 일컫겠다. 그렇다면, 그림 4의 상황이라면 그림 3과 같은 세 개의 개구리 경로가 있다고 말할 수 있다. (물론 다른 가짓수도 있을 수 있다.)

한편, 첫째 칸에서 수직으로 내려가는 경로는 간격이 4인 개구리 경로일 수도 있지만, 이 경로의 영향을 받은 벼는 두 포기밖에 없기 때문에 고려하지 않는다. 그리고 둘째 줄 셋째 칸(2, 3), 셋째 줄 넷째 칸(3, 4), 여섯째 줄 일곱째(6, 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 

입력      

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

번역: po10003
출처:IOI 2002

In Korea, the naughtiness of the cheonggaeguri, a small frog, is legendary. This is a well-deserved reputation, because the frogs jump through your rice paddy at night, flattening rice plants. In the morning, after noting which plants have been flattened, you want to identify the path of the frog which did the most damage. A frog always jumps through the paddy in a straight line, with every hop the same length:

Your rice paddy has plants arranged on the intersection points of a grid as shown in Figure-1, and the troublesome frogs hop completely through your paddy, starting outside the paddy on one side and ending outside the paddy on the other side as shown in Figure-2:

Many frogs can jump through the paddy, hopping from rice plant to rice plant. Every hop lands on a plant and flattens it, as in Figure-3. Note that some plants may be landed on by more than one frog during the night. Of course, you can not see the lines showing the paths of the frogs or any of their hops outside of your paddy . for the situation in Figure-3, what you can see is shown in Figure-4:

From Figure-4, you can reconstruct all the possible paths which the frogs may have followed across your paddy. You are only interested in frogs which have landed on at least 3 of your rice plants in their voyage through the paddy. Such a path is said to be a frog path. In this case, that means that the three paths shown in Figure-3 are frog paths (there are also other possible frog paths). The vertical path down column 1 might have been a frog path with hop length 4 except there are only 2 plants flattened so we are not interested; and the diagonal path including the plants on row 2 col. 3, row 3 col. 4, and row 6 col. 7 has three flat plants but there is no regular hop length which could have spaced the hops in this way while still landing on at least 3 plants, and hence it is not a frog path. Note also that along the line a frog path follows there may be additional flattened plants which do not need to be landed on by that path (see the plant at (2, 6) on the horizontal path across row 2 in Figure-4), and in fact some flattened plants may not be explained by any frog path at all.

Your task is to write a program to determine the maximum number of landings in any single frog path (where the maximum is taken over all possible frog paths). In Figure-4 the answer is 7, obtained from the frog path across row 6.

입력

Your program is to read from standard input. The first line contains two integers R and C, respectively the number of rows and columns in your rice paddy, 1 ￡ R,C ￡ 5000. The second line contains the single integer N, the number of flattened rice plants, 3 ￡ N ￡ 5000. Each of the remaining N lines contains two integers, the row number (1￡ row number ￡ R) and the column number (1￡ column number ￡ C) of a flattened rice plant, separated by one blank. Each flattened plant is only listed once.

출력

Your program is to write to standard output. The output contains one line with a single integer, the number of plants flattened along a frog path which did the most damage if there exists at least one frog path, otherwise, 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



입력

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



출처:IOI 2002
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]