# Land Inheritance

Ԑ : 8 sec, : 524288 KB

## F - yn

### Problem Statement

$N$ ľZ͐ëY̘bĂD ނ̐e̎cȈY̒ɂ͍Lȓyn܂܂ĂD ̓yn͓k $H$ km, $W$ km ɍL钷̌ĂD ̓yn 1 km l̋PʂŊǗĂC yn̖k[ $i$  $i+1$ km [ $j$  $j+1$ km ͈̔͂ɂ 1 km l̋ $(i, j)$ ƌĂԁD i$i$, $j$ $0 \leq i < H$, $0 \leq j < W$ 𖞂łDj yn̉i͋悲ƂɌ܂ĂC $(i, j)$ ̉i $a_{i, j}$ ŕ\D

Ẑ͎悤ɓyn𕪂đ邱ƂɂD

• $N$ ľZ킻ꂼꂪIёD
• eZ킪yn 1 ̒𐬂悤ɋI΂Ȃ΂ȂȂD
• $N$ ľZ킪yn͏dȂĂ͂ȂȂD
• NȂ悪Ă悢DNȂ͕D

lyn͈̔͂Ɋ܂܂̉i̘a̓yn̉iƌĂԁD ŹCeXyn̉iȂׂɂȂ悤ɓyn𕪂D Ȃ̎d́C $N$ l̒őyn̉i łႢl̓yn̉iőɂ悤ȓyn̕l邱ƂłD ̂悤ɓyn𕪂́Cyn̉iłႢl̓yn̉i𓚂vO쐬D

### Input

͈͂ȉ̂悤Ȍŗ^D

$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)$ ͈Y̓yn̓k̒Ɠ̒ꂼ\D $N$ $(2 \leq N \leq 4)$ ͓yn𑊑Z̐l\D $a_{i, j}$ $(0 \leq a_{i,j} \leq 10^4)$ ͋ $(i, j)$ ̉i\D

### Output

yn̉iłႢl̓yn̉iőɂ悤ɕ́C łႢyn̉i 1 sŏo͂D

### Sample Input 1

3 3 2
1 2 2
3 1 0
0 4 3

### Output for the Sample Input 1

7

}̂悤ɕ̂œKłD

### Sample Input 2

3 3 2
0 1 0
1 1 1
0 1 0

### Output for the Sample Input 2

1

### Sample Input 3

2 5 3
8 3 0 5 6
2 5 2 5 2

### Output for the Sample Input 3

11

### Sample Input 4

3 3 4
3 3 4
3 3 4
3 3 4

### Output for the Sample Input 4

7

### Sample Input 5

4 4 4
2 2 2 2
2 1 2 1
2 2 2 2
2 1 2 1

### Output for the Sample Input 5

7

Source: ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2016 , Japan, 2016-04-24
http://jag-icpc.org/
http://jag2016-domestic.contest.atcoder.jp/