Format

Sample 1

Input

3 4 0
1 2 3 4
9 8 7 6
5 4 7 2

Output

34

Sample 2

Input

5 5 1
9 9 9 0 0
0 0 9 0 0
0 0 0 0 0
0 0 9 0 0
9 0 9 9 9

Output

81

Limitation

2s, 512MiB for each test case.