시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 125 36 34 34.343%

문제

세준이는 N개의 빈 칸이 있는 R*C크기의 체스판을 가지고 있다. 빈 칸에는 룩을 놓을 수 없지만, 공격을 할 수 있는지 없는지에는 영향을 미치지 않는다. 즉, 빈 칸을 사이에 두고도 공격을 할 수 있다.

R*C크기의 체스판에 최대 몇 개의 룩을 놓을 수 있는지 구하는 프로그램을 작성하시오. 룩은 자기와 같은 행 또는 열에 다른 룩이 있으면 잡을 수 있다.

입력

첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼쪽 열은 1번 열이다. R과 C는 300보다 작거나 같은 자연수이고, N은 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 최대 몇 개의 룩을 놓을 수 있는지 출력한다.

예제 입력

3 3 6
1 1
2 1
2 2
3 1
3 2
3 3

예제 출력

2

힌트

출처