22097번 - Нанороботы 다국어

문제

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

Все роботы получают команды с сервера. К сожалению, серверный софт пока тоже не доработан. В частности, в каждый момент времени пользоваться сервером может только какой-то один робот. Второму подключившемуся придётся дождаться выполнения команды первого, чтобы выполнить свою. Таким образом общее время выполнения роботами некоторых действий равно суммарному числу команд, полученных ими от сервера.

Робот, состоящий из w нанороботов, изначально установлен в левом верхнем углу испытательного полигона размером n × m клеток. Его цель — добраться всеми своими нанороботами до правого нижнего угла испытательного полигона. Каждая клетка полигона имеет ограничение, какое максимальное число нанороботов может на ней одновременно находиться.

Робот может послать команду серверу и получить команду движения на одну клетку в каком-то из четырёх направлений. Также, если робот в настоящий момент состоит из x нанороботов, он может получить команду разделиться на двух роботов, состоящих из u и v нанороботов, соответственно, где u + v = x. После этого эти два робота действуют независимо. Объединиться обратно роботы не могут.

Помогите проверить оптимальность используемого алгоритма перемещения — посчитайте, какое наименьшее количество команд сервер должен послать, чтобы все нанороботы переместились в правый нижний угол полигона.

입력

В первой строке заданы целые числа n, m и w (1 ≤ n, m ≤ 10, nm ≥ 2, 1 ≤ w ≤ 500). Далее, в n строках задано по m положительных целых чисел a_{i, j} — максимальное число нанороботов, которые могут находиться в клетке i-й строки j-го столбца (a_{i, j} ≤ 500). Гарантируется, что в начальной и конечной клетках могут находиться хотя бы w роботов.

출력

Выведите единственное число — ответ на задачу.

제한

힌트