나노로봇

어느 비밀 연구소 깊은 곳에서 액체 로봇의 시제품을 개발하고 있다. 이 로봇은 사실 독립적으로 제어되는 수많은 나노로봇으로 이루어져 있으며, 이들이 동작을 조율해 원하는 거대 구조를 이룬다. 연구는 아직 끝나기 멀었다. 함께 사용하는 나노로봇의 수가 적고, 이동 알고리즘도 만족스럽지 못하다.

모든 로봇은 서버에서 명령을 받는다. 아쉽게도 서버 소프트웨어도 아직 완성되지 않았다. 특히 어느 순간에든 서버를 쓸 수 있는 로봇은 하나뿐이다. 두 번째로 접속한 로봇은 첫 번째 로봇의 명령이 끝날 때까지 기다려야 자기 명령을 수행할 수 있다. 따라서 로봇들이 어떤 동작을 수행하는 데 걸리는 전체 시간은 이들이 서버에서 받은 명령의 총 개수와 같다.

w개의 나노로봇으로 이루어진 로봇이 처음에 n × m칸 크기의 시험장 왼쪽 위 모서리에 놓여 있다. 목표는 모든 나노로봇을 시험장 오른쪽 아래 모서리로 옮기는 것이다. 시험장의 각 칸에는 동시에 있을 수 있는 나노로봇의 최대 수에 대한 제한이 있다.

로봇은 서버에 명령을 보내 네 방향 중 한 방향으로 한 칸 이동하는 명령을 받을 수 있다. 또 로봇이 현재 x개의 나노로봇으로 이루어져 있으면, u + v = x인 u개와 v개의 나노로봇으로 이루어진 두 로봇으로 분할하는 명령을 받을 수 있다. 그 뒤 두 로봇은 독립적으로 움직인다. 로봇들은 다시 합칠 수 없다.

사용 중인 이동 알고리즘의 최적성을 확인하도록 돕자. 모든 나노로봇이 시험장 오른쪽 아래 모서리로 이동하려면 서버가 보내야 하는 명령의 최소 개수를 구하라.

첫째 줄에 정수 n, m, w가 주어진다(1 ≤ n, m ≤ 10, nm ≥ 2, 1 ≤ w ≤ 500). 다음 n개 줄에 각각 m개의 양의 정수 a**i, j가 주어지는데, 이는 i번째 줄 j번째 열의 칸에 동시에 있을 수 있는 나노로봇의 최대 수이다(a**i, j ≤ 500). 시작 칸과 끝 칸에는 적어도 w개의 로봇이 있을 수 있음이 보장된다.

문제의 답을 나타내는 정수 하나를 출력한다.