You are given a city in the form of a cells grid of size $$$N \times M$$$. You are allowed to place $$$K$$$ fire stations at any cell on the grid $$$\bf{(at\ integer\ coordinates)}$$$.
Fire station fire fighter can move in $$$8$$$ directions (up, down, left, right, diagonals).
The distance from a station at cell $$$(x_1, y_1)$$$ to cell $$$(x_2, y_2)$$$ is defined as:
You want to place the fire stations optimally so that every cell in the grid is within $$$distance \le d$$$ from at least one station. Your task is to find the smallest possible value of $$$d$$$ that guarantees full coverage.
The first and only line contains 3 integers $$$N,M,K$$$ ($$$1 \le N, M \le 10^9$$$, $$$1 \le K \le 10^5$$$) — dimensions of the grid, and the number of fire stations available, respectively.
Print a single integer — the minimum value of $$$d$$$.
5 5 4
1
2000 12 26
38
The distribution for the first sample provided above:
