한 회사가 직사각형 모양의 방을 청소하기 위해 정사각형 모양의 청소 로봇을 구매하려고 합니다. 방의 일부는 장애물로 막혀 있습니다.

다양한 크기의 로봇이 있습니다. 각 로봇은 로봇의 어떤 부분도 장애물과 겹치지 않는다면 방 안에서 가로 및 세로로 이동할 수 있습니다. 로봇은 방향을 바꿀 수 없으므로 항상 축에 평행하게 이동합니다. 더 큰 로봇은 작업을 더 빨리 끝낼 수 있지만 장애물에 의해 방해받을 가능성이 더 높습니다. 로봇은 항상 방의 경계를 벗어나지 않고 완전히 방 안에 머물러야 합니다.

장애물이 없는 방의 모든 정사각형 구역을 청소할 수 있는 가장 큰 로봇의 크기는 얼마입니까?

입력

첫 번째 줄에는 세 정수 $n, m$ ($3 \le n, m$ 이고 $n \cdot m \le 5 \cdot 10^6$)과 $k$ ($0 \le k < n \cdot m, k < 10^6$)가 주어집니다. 여기서 $n$과 $m$은 방의 가로 및 세로 치수(인치 단위)이며, $k$는 장애물의 개수입니다.

다음 $k$개의 줄에는 각각 두 정수 $i$와 $j$ ($1 \le i \le n, 1 \le j \le m$)가 주어집니다. 이는 $(i, j)$ 위치의 1인치 정사각형 구역이 장애물로 막혀 있음을 나타냅니다. 모든 장애물 구역은 서로 다릅니다.

출력

방 전체를 청소할 수 있는 가장 큰 정사각형 로봇의 한 변의 길이를 출력하십시오. 만약 방 전체를 청소할 수 있는 로봇이 없다면 $-1$을 출력하십시오.

예제

입력 1

10 7 1
8 3

출력 1

2