토지 상속

$N$ 명의 형제가 부모님이 남긴 넓은 토지를 나누어 상속하려고 한다. 토지는 남북 $H$ km, 동서 $W$ km인 직사각형이다. 토지는 1 km 사각형 구획 단위로 관리되며, 북쪽 끝에서 $i$ km에서 $i+1$ km, 서쪽 끝에서 $j$ km에서 $j+1$ km 범위에 있는 구획을 구획 $(i, j)$라고 부른다. 여기서 $i$, $j$는 $0 \leq i < H$, $0 \leq j < W$를 만족하는 정수이다. 구획마다 가격이 정해져 있으며, 구획 $(i, j)$의 가격은 $a_{i,j}$이다.

형제는 다음과 같이 토지를 나누어 상속한다.

• $N$ 명의 형제가 각각 구획을 몇 개 골라 상속한다.
• 각 형제가 상속하는 토지는 하나의 직사각형을 이루어야 한다.
• $N$ 명이 상속하는 토지는 서로 겹치면 안 된다.
• 아무도 상속하지 않는 구획이 있어도 된다. 상속자가 없는 구획은 버려진다.

어떤 사람이 상속하는 토지에 포함된 구획 가격의 합을 그 토지의 가격이라고 한다. 형제는 각자 상속하는 토지의 가격이 되도록 공평해지기를 원한다. $N$ 명 중 상속하는 토지의 가격이 가장 낮은 사람의 가격을 최대로 만드는 분할 방법을 찾고, 그때의 가장 낮은 토지 가격을 구하라.

입력은 다음 형식으로 주어진다.

H W N
a_{0,0} a_{0,1} ... a_{0,W-1}
...
a_{H-1,0} a_{H-1,1} ... a_{H-1,W-1}

$H$, $W$ ($2 \leq H, W \leq 200$)는 토지의 남북 길이와 동서 길이를 나타낸다. $N$ ($2 \leq N \leq 4$)은 토지를 상속하는 형제의 수이다. $a_{i,j}$ ($0 \leq a_{i,j} \leq 10^4$)는 구획 $(i, j)$의 가격이다.

토지를 가장 낮은 토지 가격이 최대가 되도록 나누었을 때, 그 가장 낮은 토지 가격을 한 줄에 출력하라.