세상에서 제일 착한 다솜

다솜이는 눈이 온 아침마다 테라스에 나가 발자국을 남기는 일을 좋아한다. 늦게 일어나는 조교는 이미 남아 있는 발자국만 보고 누가 어떤 길로 지나갔는지 추측해야 한다. 어느 날 아침, 조교는 다솜이의 발자취를 찾고 싶었지만, 이미 많은 학생이 테라스를 오간 뒤라 흔적을 구분하기가 쉽지 않았다.

확실한 것은 학생들이 항상 일직선으로 이동하고, 같은 학생의 발걸음 간격은 일정하다는 점이다.

위 그림처럼 다솜이를 포함한 학생들의 이동 방향과 보폭은 서로 다를 수 있다.

학생들은 테라스 밖에서 들어와 한 직선을 따라 일정한 보폭으로 눈을 밟고 지나간다.

그림 3	그림 4

그림 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, C 이하이다. 같은 칸을 여러 학생이 밟았더라도 그 좌표는 한 번만 주어진다.

다솜이가 남긴 것으로 추정할 수 있는 경로 중 발자국 수가 가장 많은 경로의 발자국 수를 출력한다. 조건을 만족하는 학생 경로를 하나도 찾을 수 없다면 0을 출력한다.