Uber is planning to roll out driver hubs across a new city.

The city is represented as a w × h grid, where each cell represents a neighborhood.

You must place exactly n driver hubs such that the maximum distance from any cell to its nearest hub is minimized.

Movement Rules

Distance is calculated using Manhattan Distance.

Movement allowed: up, down, left, right.

No diagonal movement.

Your task is to compute the minimum possible value of the maximum shortest distance from any cell to its closest hub.

int findMinDistance(int w, int h, int n)

Example

Input: w = 4 h = 4 n = 3

One optimal placement produces a maximum distance of: 2

Example distance grid (0 = hub location):

1 0 1 2

2 1 2 1

1 0 1 0

2 1 2 1

So the answer is: 2