Một công ty muốn mua một robot làm sạch hình vuông để dọn dẹp một căn phòng hình chữ nhật. Một số phần của căn phòng bị chặn bởi các vật cản.

Có nhiều loại robot với kích thước khác nhau. Mỗi robot có thể di chuyển theo chiều ngang và chiều dọc trong phòng nếu không có phần nào của robot đè lên vật cản. Robot không thể thay đổi hướng, vì vậy các chuyển động luôn song song với các trục tọa độ. Robot lớn hơn sẽ hoàn thành công việc nhanh hơn nhưng dễ bị cản trở bởi các vật cản hơn. Robot phải luôn nằm hoàn toàn trong phòng và không được có phần nào vượt ra ngoài các cạnh của hình chữ nhật.

Kích thước lớn nhất của robot mà công ty có thể mua để có thể làm sạch tất cả các ô vuông trong phòng không bị chiếm bởi vật cản là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n, m$ ($3 \le n, m$ và $n \cdot m \le 5 \cdot 10^6$) và $k$ ($0 \le k < n \cdot m, k < 10^6$), trong đó $n$ và $m$ là kích thước của căn phòng tính bằng inch, và $k$ là số lượng vật cản.

Mỗi dòng trong số $k$ dòng tiếp theo chứa hai số nguyên $i$ và $j$ ($1 \le i \le n, 1 \le j \le m$). Dữ liệu này chỉ ra rằng ô vuông một inch tại $(i, j)$ bị chặn. Tất cả các ô bị chặn là riêng biệt.

Dữ liệu ra

In ra một số nguyên duy nhất là độ dài cạnh lớn nhất của robot hình vuông có thể làm sạch toàn bộ căn phòng, hoặc $-1$ nếu không có robot nào như vậy có thể làm sạch toàn bộ căn phòng.

Ví dụ

Dữ liệu vào 1

10 7 1
8 3

Dữ liệu ra 1

2