#include<iostream>
#include<queue>
#include<map>
#include<cassert>
#include<cstring>
#include<climits>
using namespace std;
int W, H, N;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
int calc(int i, int j) {
if(W <= H)
return i + W * j;
return H * i + j;
}
bool get(int bitmask, int i, int j) {
return (bitmask&(1<<calc(i,j)));
}
int bfs(int bitmask) {
int dist[W][H];
memset(dist, -1, sizeof dist);
int maxDist = 0;
queue<pair<int,int>> Q;
for(int i = 0; i < W; i++)
for(int j = 0; j < H; j++)
if(get(bitmask, i, j)) {
dist[i][j] = 0;
Q.push({i, j});
}
assert(Q.size() == N);
while(!Q.empty()) {
int x = Q.front().first;
int y = Q.front().second;
maxDist = max(maxDist, dist[x][y]);
Q.pop();
for(int d = 0; d < 4; d++) {
int newx = x + dx[d];
int newy = y + dy[d];
if(newx >= W || newy >= H || newx < 0 || newy < 0)
continue;
if(dist[newx][newy] == -1) {
dist[newx][newy] = dist[x][y] + 1;
Q.push({newx, newy});
}
}
}
/*
for(int i = 0; i < W; i++) {
for(int j = 0; j < H; j++)
cout << get(bitmask, i, j) << ' ';
cout << '\n';
}
cerr << "^ VAL IS = " << maxDist << "\n\n";
*/
return maxDist;
}
map<pair<int,int>, int> dp;
int solve(int bitmask, int left) {
if(left == 0) {
return bfs(bitmask);
}
if(dp.find({bitmask, left}) != dp.end()) {
return dp[{bitmask, left}];
}
int minDistance = INT_MAX;
for(int i = 0; i < W; i++)
for(int j = 0; j < H; j++)
if(!get(bitmask, i, j)) {
int val = solve((bitmask|(1<<calc(i, j))), left-1);
minDistance = min(minDistance, val);
}
return dp[{bitmask, left}] = minDistance;
}
int main() {
while(cin >> W >> H >> N) {
dp.clear();
cout << solve(0, N) << '\n';
}
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPGNhc3NlcnQ+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPGNsaW1pdHM+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgVywgSCwgTjsKCmludCBkeFtdID0gezEsIC0xLCAwLCAwfTsKaW50IGR5W10gPSB7MCwgMCwgLTEsIDF9OwoKaW50IGNhbGMoaW50IGksIGludCBqKSB7CglpZihXIDw9IEgpCgkJcmV0dXJuICBpICsgVyAqIGo7CglyZXR1cm4gSCAqIGkgKyBqOwp9Cgpib29sIGdldChpbnQgYml0bWFzaywgaW50IGksIGludCBqKSB7CglyZXR1cm4gKGJpdG1hc2smKDE8PGNhbGMoaSxqKSkpOwp9CgppbnQgYmZzKGludCBiaXRtYXNrKSB7CglpbnQgZGlzdFtXXVtIXTsKCW1lbXNldChkaXN0LCAtMSwgc2l6ZW9mIGRpc3QpOwoJCglpbnQgbWF4RGlzdCA9IDA7CglxdWV1ZTxwYWlyPGludCxpbnQ+PiBROwoJCglmb3IoaW50IGkgPSAwOyBpIDwgVzsgaSsrKQoJCWZvcihpbnQgaiA9IDA7IGogPCBIOyBqKyspCgkJCWlmKGdldChiaXRtYXNrLCBpLCBqKSkgewoJCQkJZGlzdFtpXVtqXSA9IDA7CgkJCQlRLnB1c2goe2ksIGp9KTsKCQkJfQogCWFzc2VydChRLnNpemUoKSA9PSBOKTsKCQoJd2hpbGUoIVEuZW1wdHkoKSkgewoJCWludCB4ID0gUS5mcm9udCgpLmZpcnN0OwoJCWludCB5ID0gUS5mcm9udCgpLnNlY29uZDsKCQltYXhEaXN0ID0gbWF4KG1heERpc3QsIGRpc3RbeF1beV0pOwoJCVEucG9wKCk7CgkJCgkJZm9yKGludCBkID0gMDsgZCA8IDQ7IGQrKykgewoJCQlpbnQgbmV3eCA9IHggKyBkeFtkXTsKCQkJaW50IG5ld3kgPSB5ICsgZHlbZF07CgkJCQoJCQlpZihuZXd4ID49IFcgfHwgbmV3eSA+PSBIIHx8IG5ld3ggPCAwIHx8IG5ld3kgPCAwKQoJCQkJY29udGludWU7CgkJCWlmKGRpc3RbbmV3eF1bbmV3eV0gPT0gLTEpIHsKCQkJCWRpc3RbbmV3eF1bbmV3eV0gPSBkaXN0W3hdW3ldICsgMTsKCQkJCVEucHVzaCh7bmV3eCwgbmV3eX0pOwoJCQl9CgkJfQoJfQoJCi8qCQoJZm9yKGludCBpID0gMDsgaSA8IFc7IGkrKykgewoJCWZvcihpbnQgaiA9IDA7IGogPCBIOyBqKyspCgkJCWNvdXQgPDwgZ2V0KGJpdG1hc2ssIGksIGopIDw8ICcgJzsKCQljb3V0IDw8ICdcbic7Cgl9CgljZXJyIDw8ICJeIFZBTCBJUyA9ICIgPDwgbWF4RGlzdCA8PCAiXG5cbiI7CiovCglyZXR1cm4gbWF4RGlzdDsKfQoKbWFwPHBhaXI8aW50LGludD4sIGludD4gZHA7CgppbnQgc29sdmUoaW50IGJpdG1hc2ssIGludCBsZWZ0KSB7CglpZihsZWZ0ID09IDApIHsKCQlyZXR1cm4gYmZzKGJpdG1hc2spOwoJfQoJaWYoZHAuZmluZCh7Yml0bWFzaywgbGVmdH0pICE9IGRwLmVuZCgpKSB7CgkJcmV0dXJuIGRwW3tiaXRtYXNrLCBsZWZ0fV07Cgl9CglpbnQgbWluRGlzdGFuY2UgPSBJTlRfTUFYOwoJZm9yKGludCBpID0gMDsgaSA8IFc7IGkrKykKCQlmb3IoaW50IGogPSAwOyBqIDwgSDsgaisrKQoJCQlpZighZ2V0KGJpdG1hc2ssIGksIGopKSB7CgkJCQlpbnQgdmFsID0gc29sdmUoKGJpdG1hc2t8KDE8PGNhbGMoaSwgaikpKSwgbGVmdC0xKTsKCQkJCW1pbkRpc3RhbmNlID0gbWluKG1pbkRpc3RhbmNlLCB2YWwpOwoJCQl9CglyZXR1cm4gZHBbe2JpdG1hc2ssIGxlZnR9XSA9IG1pbkRpc3RhbmNlOwp9CgppbnQgbWFpbigpIHsKCXdoaWxlKGNpbiA+PiBXID4+IEggPj4gTikgewoJCWRwLmNsZWFyKCk7CgkJY291dCA8PCBzb2x2ZSgwLCBOKSA8PCAnXG4nOwoJfQp9Cg==