로봇 연구원인 당신은 방금 비밀병기 로봇을 완성했다. 이 로봇은 $w$개의 나노로봇으로 구성되어 있으며, 각 나노로봇은 언제든지 분리되어 독립적으로 움직일 수 있다.
모든 나노로봇은 하나의 서버로부터 명령을 받아 움직인다. 아쉽게도 서버 소프트웨어의 개발이 완료되지 않아서, 한 번에 하나의 로봇에게만 명령을 내릴 수 있다. 즉, 로봇이 명령을 수행하는데 걸리는 시간은 명령의 개수와 같다.
당신은 테스트를 위해 로봇을 실험실에 설치했다. 실험실은 가로 $m$칸, 세로 $n$칸의 격자 모양이며, 로봇은 맨 왼쪽 위칸에 설치되어 있다. 이번 테스트의 목표는 로봇을 맨 오른쪽 아래칸으로 이동하는 것이다. 단, 각 격자칸마다 동시에 올라갈 수 있는 나노로봇의 수가 제한되어 있다.
서버를 통해 로봇에 내릴 수 있는 명령은 다음 두 가지 중 하나이다.
상하좌우 인접한 칸 중 하나로 이동 : 실험실 밖으로는 이동할 수 없다.
로봇을 분리 : 현재 $x$개의 나노로봇으로 구성된 로봇에게 $u+v=x$를 만족하는 두 양의 정수 $u$,$v$를 골라 나노로봇 $u$개로 구성된 로봇과 나노로봇 $v$개로 구성된 로봇으로 분리한다.
분리된 두 로봇은 별개의 로봇으로 간주되며, 분리된 후에는 각 로봇에게 명령을 따로 내려야 한다. 재결합은 불가능하다.
테스트의 목표를 달성하기 위해 필요한 명령 수의 최솟값을 구하라.
입력
첫 번째 줄에는 문제에 언급된 정수 $n$, $m$, $w$가 공백으로 구분되어 주어진다. $(1 \le n,m \le 10,\;nm \ge 2,\; 1 \le w \le 500)$
두 번째 줄부터 $n$개의 줄에는, 각각 $m$개의 정수 $a_{i,j}$가 주어진다. $i$번째 줄에 $j$번째로 주어지는 양의 정수 $a_{i,j}(a_{i,j} \le 500)$는 실험실의 $i$번째 행 $j$번째 열에 동시에 있을 수 있는 나노로봇의 수를 뜻한다.
iktk 2년 전
문제
로봇 연구원인 당신은 방금 비밀병기 로봇을 완성했다. 이 로봇은 $w$개의 나노로봇으로 구성되어 있으며, 각 나노로봇은 언제든지 분리되어 독립적으로 움직일 수 있다.
모든 나노로봇은 하나의 서버로부터 명령을 받아 움직인다. 아쉽게도 서버 소프트웨어의 개발이 완료되지 않아서, 한 번에 하나의 로봇에게만 명령을 내릴 수 있다. 즉, 로봇이 명령을 수행하는데 걸리는 시간은 명령의 개수와 같다.
당신은 테스트를 위해 로봇을 실험실에 설치했다. 실험실은 가로 $m$칸, 세로 $n$칸의 격자 모양이며, 로봇은 맨 왼쪽 위칸에 설치되어 있다. 이번 테스트의 목표는 로봇을 맨 오른쪽 아래칸으로 이동하는 것이다. 단, 각 격자칸마다 동시에 올라갈 수 있는 나노로봇의 수가 제한되어 있다.
서버를 통해 로봇에 내릴 수 있는 명령은 다음 두 가지 중 하나이다.
테스트의 목표를 달성하기 위해 필요한 명령 수의 최솟값을 구하라.
입력
첫 번째 줄에는 문제에 언급된 정수 $n$, $m$, $w$가 공백으로 구분되어 주어진다. $(1 \le n,m \le 10,\;nm \ge 2,\; 1 \le w \le 500)$
두 번째 줄부터 $n$개의 줄에는, 각각 $m$개의 정수 $a_{i,j}$가 주어진다. $i$번째 줄에 $j$번째로 주어지는 양의 정수 $a_{i,j}(a_{i,j} \le 500)$는 실험실의 $i$번째 행 $j$번째 열에 동시에 있을 수 있는 나노로봇의 수를 뜻한다.
출발점과 도착점에 $w$개의 나노로봇이 동시에 있을 수 있는 데이터만 주어진다.
출력
문제의 정답을 정수 하나로 출력한다.