Chocolate Bar

Time limit1sMemory limit2048 MB

Summary

Given an N by M chocolate bar and a target area K, find the fewest splits needed so that some pieces total exactly K.

Level: Medium5 of 10
Topics: Math, Brute force
Solved: No attempts yet

Problem

You have a chocolate bar shaped like a rectangle. Originally, the bar has width $N$ and height $M$ . In this problem, $(n \times m)$ denotes a chocolate bar with width $n$ and height $m$ .

You want to eat chocolate with a total area of exactly $K$ . However, you always eat a bar as a whole. If you eat a bar $(n \times m)$ , you eat all of its area $n \cdot m$ .

You may perform any of the following operations any number of times, including zero.

Pick one bar $(n \times m)$ and split it into two bars $(n \times i)$ and $(n \times (m - i))$ , where $i$ is an integer with $1 \le i < m$ .
Pick one bar $(n \times m)$ and split it into two bars $(i \times m)$ and $((n - i) \times m)$ , where $i$ is an integer with $1 \le i < n$ .

Find the minimum number of operations needed so that you can eat some bars with a total area of exactly $K$ .

Input

Three integers $N$ , $M$ , and $K$ are given ( $1 \le N, M \le 10^6$ , $1 \le K \le N \cdot M$ ).

Output

Print a single integer, the minimum number of operations needed so that some bars can be eaten with a total area of exactly $K$ .

Examples3

Example 1
Input
```
4 4 10
```
Expected output
```
2
```
Example 2
Input
```
5 6 6
```
Expected output
```
1
```
Example 3
Input
```
1 1 1
```
Expected output
```
0
```