Woburn Challenge 2016-17 Round 3 - Senior Division

You've landed a job as one of the level designers for the latest game in the Pokémon series, Pokémon Navy Green! You've always hated those nerdy Pokémon fans, always having fun with their childish Pokémon nonsense, so this is your chance to get back at them.

One of the screens in the game is a grid of cells with ~N~ rows and ~M~ columns ~(2 \le N, M \le 2\,000\,000\,000)~. The player will start in the top-left cell, with the goal of reaching the bottom-right cell by repeatedly moving up, down, left, or right.

As a level designer, you may decide that some subset of the cells in the grid should contain trees. The top-left and bottom-right cells may not contain trees, but any of the others are fair game. The player may not move into a cell which contains a tree. However, they do have the ability to teach a move called Cut to one of their Pokémon. Each time Cut is used, a single tree can be destroyed, allowing the player to move into its cell. However, Cut may only be used at most ~K~ ~(0 \le K \le 2\,000\,000\,000)~ times in total.

You love the idea of frustrating the player with a subtly impossible level, but don't want to make your treachery too obvious, for fear of losing your job before the game gets released. As such, you'd like to determine the minimum number of trees that must be present on the grid such that it's impossible for the player to move from the top-left cell to the bottom-right one, even after optimally using Cut at most ~K~ times. Unfortunately, it may also be the case that the level will be possible to complete no matter how many trees you place on the grid.

In test cases worth ~10/12~ of the points, ~N \le 10^6~ and ~M \le 10^6~.

Input Specification

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

Output Specification

Output one line consisting of a single integer – the minimum number of trees required to make the level impossible, or -1 if no number of trees will suffice.
Note that the answer may not necessarily fit within a ~32~-bit signed integer (you may need the long long type in C++, or long in Java).

Sample Input 1

2 5 2

Sample Output 1

6

Sample Explanation 1

One optimal arrangement of trees is shown below (trees are indicated with #, while empty cells are indicated with .):

.###.
.###.

If the players cut down any ~2~ of these ~6~ trees, they still won't be able to move from the top-left to the bottom-right cell.

Sample Input 2

2 5 4

Sample Output 2

-1

Sample Explanation 2

Even if trees are placed in all ~8~ valid cells, the player will still be able to move from the top-left to the bottom-right cell after cutting down ~4~ of them.