28416번 - Видеонаблюдение 서브태스크다국어

Безопасность в здании торгового центра обеспечивается с помощью системы видеонаблюдения. На компьютере у охранника открыта программа, которая выводит на экран видеопотоки с нескольких камер. Эта программа устроена следующим образом: на экране представлена прямоугольная сетка, состоящая из $h$ строк и $w$ столбцов. Каждая из ячеек может быть пуста, либо туда выводится изображение с одной из камер. Для управления расположением изображений в программе, сотрудник службы безопасности может использовать кнопки <<влево>>, <<вправо>>, <<вверх>> и <<вниз>>.

Кнопка <<влево>> перемещает изображение из каждой ячейки в ячейку, находящуюся слева от нее. При этом, изображение из самой левой ячейки в каждом ряду перемещается в самую правую ячейку этого ряда.

Аналогичным образом действуют кнопки <<вправо>>, <<вверх>> и <<вниз>>. Кнопка <<вправо>> перемещает изображение из каждой ячейки в ячейку, находящуюся справа от нее. Изображения из самой правой ячейки в каждом ряду перемещаются в самую левую ячейку этого ряда. Кнопка <<вверх>> перемещает изображение из каждой ячейки в ячейку, находящуюся над ней. Изображения из самого верхнего ряда перемещаются в ячейки самого нижнего ряда. Кнопка <<вниз>> перемещает изображение из каждой ячейки в ячейку, находящуюся под ней. Изображения из самого нижнего ряда перемещаются в ячейки самого верхнего ряда.

Строки в сетке пронумерованы сверху вниз, столбцы пронумерованы слева направо. Ячейка на пересечении строки номер $r$ и столбца номер $c$ обозначается как $(r, c)$.

Ниже изображена сетка с $3$ строками, $4$ столбцами и тремя ячейками, содержащими изображения, с координатами $(1, 1)$, $(2, 4)$ и $(3, 3)$. А также изображено, куда перейдут эти изображения при нажатии на каждую из четырёх кнопок.

Охраннику удобнее, чтобы ячейки на мониторе, которые содержат изображение с камер, были расположены как можно компактнее. Компактностью изображений назовём минимальную площадь подпрямоугольника сетки, который содержит все показываемые изображения. Заметим, что с помощью кнопок можно изменять компактность. Например, в левой части рисунка ниже показано расположение изображений, которое имеет компактность $12$. Если один раз нажать на кнопку <<вправо>> и один раз нажать на кнопку <<вверх>>, компактность изображений станет равна $4$.

Вам дана сетка, которая содержит $k$ ячеек с изображениями. Вычислите минимальную компактность, которую можно достичь, используя кнопки <<влево>>, <<вправо>>, <<вверх>> и <<вниз>>, а также минимальное необходимое для этого количество нажатий на кнопки.

В первой строке даны три целых числа $h$, $w$ и $k$ --- размеры сетки и количество ячеек с изображением ($1 \le h, w \le 10^9$; $1 \le k \le 100\,000$).

В каждой из следующих $k$ строк даны по два целых числа $r_i$ и $c_i$ --- координаты ячейки, содержащей изображение ($1 \le r_i \le h$; $1 \le c_i \le w$). Гарантируется, что все $k$ ячеек различны.

Выведите два целых числа --- минимальную компактность расположения изображений, которой можно достичь, используя кнопки, и минимально необходимое для достижения этой компактности количество нажатий на кнопки.