Woburn Challenge 2017-18 Round 4 - Senior Division

The Infinity War has begun! Black Panther is well aware of the importance of rallying his supporters together to help defend Earth from the evil Thanos, so he's working on unifying the Wakandan army. Unbeknownst to him, however, Loki has formed a secret alliance with Thanos and is planning on sabotaging Black Panther's efforts.

The nation of Wakanda consists of $N\times M$ cities $(2\le N,M\le 1000)$, arranged in a grid with $N$ rows and $M$ columns. In each of the $M$ columns of the grid, there are $N-1$ vertical roads connecting pairs of vertically-adjacent cities. Additionally, in the bottom-most and top-most rows only, there are $M-1$ horizontal roads connecting pairs of horizontally-adjacent cities. As such, there are $M(N-1)+2(M-1)$ roads in total throughout Wakanda. Each road is exactly $1$ km long.

For example, if $N=2$ and $M=4$, the network of cities and roads looks as follows:

Loki has the explosive resources to destroy $K$ $(0\le K<M(N-1)+2(M-1))$ roads of his choice. He'd hate for any of his explosives to go to waste, so he'll destroy exactly $K$ roads, no fewer.

Upon realizing that some roads have been destroyed, Black Panther will still do his best to assemble the Wakandan army together. He'll ask soldiers to travel amongst various cities which are still connected by the remaining roads. Overall, the amount of time required for this mobilization will depend on a single factor – the maximum shortest distance (along undestroyed roads) between any pair of cities which are still reachable from one another at all. In other words, if $D_{i,j}$ is equal to the shortest distance between cities $i$ and $j$ if they're connected by roads (or is equal to $0$ if they're not connected), then the value of importance is $max\{D_{i,j}\}$ over all pairs of cities $(i,j)$.

For example, if Loki were to destroy the two roads indicated in red below, then the maximum shortest path between any pair of connected cities would be $3$ km long (for example, between the two cities marked in green, along the roads indicated in blue).

Naturally, Loki is interested in selecting a set of $K$ roads to destroy such that this value is maximized. Help him determine the maximum possible shortest distance between any pair of connected cities which his sabotage can result in.

Subtasks

In test cases worth $8/15$ of the points, $N=2$.

Input Specification

The first and only line of input consists of three space-separated integers, $N$, $M$, and $K$.

Output Specification

Output a single integer, the maximum achievable shortest distance between any pair of cities which are still connected (in km).

Sample Input

2 4 4

Sample Output

6

Sample Explanation

Loki may choose to destroy the four roads indicated in red below. The shortest path between the pair of cities marked in green would then be $6$ km long (consisting of the roads indicated in blue).