РОИ: 1 тур

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

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

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

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

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

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

Вам дана сетка, которая содержит \(k\) ячеек с изображениями. Вычислите минимальную компактность, которую можно достичь, используя кнопки «влево», «вправо», «вверх» и «вниз», а также минимальное необходимое для этого количество нажатий на кнопки.