Компания хочет приобрести квадратный робот-пылесос для уборки прямоугольной комнаты. Некоторые части комнаты заблокированы препятствиями.

Существуют роботы разных размеров. Каждый робот может перемещаться по комнате горизонтально и вертикально, если ни одна его часть не пересекается с препятствием. Роботы не могут менять ориентацию, поэтому их движения всегда параллельны осям координат. Более крупные роботы справляются с работой быстрее, но чаще сталкиваются с препятствиями. Робот должен всегда находиться полностью внутри комнаты, не выходя за пределы прямоугольника.

Какого максимального размера робот может купить компания, чтобы он смог очистить все квадраты комнаты, не занятые препятствиями?

Входные данные

Первая строка входных данных содержит три целых числа $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

10 7 1
8 3

Выходные данные 1

2