Chocolate Bar

시간 제한1초메모리 제한2048 MB

요약

N x M 초콜릿을 잘라 넓이의 합이 정확히 K인 조각들을 얻을 때 최소 자르기 횟수를 구합니다.

난이도: 보통10점 중 6점
유형: 수학, 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

You have a bar of chocolate which can be represented as a rectangle. Originally, the chocolate bar has a width of $N$ and a height of $M$ . For this problem, denote $(n \times m)$ as a chocolate bar with a width of $n$ and a height of $m$ .

You want to eat the chocolate with a total area of exactly $K$ . However, you always eat a chocolate bar as a whole; that is, if you eat a chocolate bar $(n \times m)$ , then you will eat all the chocolate with area $n \cdot m$ .

To be able to eat exactly $K$ total area, you are allowed to perform any of the following operations any number of times (possibly zero).

Pick one bar of chocolate $(n \times m)$ then split it into two bars: $(n \times i)$ and $(n \times (m - i))$ such that $i$ is an integer that satisfies $1 ≤ i < m$ .
Pick one bar of chocolate $(n \times m)$ then split it into two bars: $(i \times m)$ and $((n - i) \times m)$ such that $i$ is an integer that satisfies $1 ≤ i < n$ .

Determine the minimum number of operations such that it is possible to eat some chocolate bars with a total area of $K$ .

입력

Input consists of three integers $N$ $M$ $K$ ( $1 ≤ N, M ≤ 10^6$ ; $1 ≤ K ≤ N \cdot M$ ).

출력

Output a single integer representing the minimum number of operations such that it is possible to eat some chocolate bars with a total area of $K$ .

예제3

예제 1
입력
```
4 4 10
```
예상 출력
```
2
```
예제 2
입력
```
5 6 6
```
예상 출력
```
1
```
예제 3
입력
```
1 1 1
```
예상 출력
```
0
```