우주왕자 VITAS는 지구인들과 친해지기 위해 사교파티를 열었다. VITAS는 포도주 $A$병과 빵 $B$개를 가지고 있고, 포도주 한 병을 빵 한 개로 바꾸거나 빵 한 개를 포도주 한 병으로 바꾸는 마법을 최대 $K$번 부릴 수 있다.</p>

VITAS는 초대한 모든 지구인에게 각각 동일한 수의 포도주와 빵을 나눠 줄 것이다. 한 종류를 아무에게도 나눠 주지 않는 것도 가능하다. 단, 포도주와 빵을 나눠주고 난 뒤 남은 것이 있으면 안 된다.

VITAS가 위 조건을 만족시키면서 초대할 수 있는 지구인의 수의 최댓값을 구하여라.

입력 형식

첫째 줄에 정수 $A$, $B$, $K$가 공백을 사이에 두고 주어진다. $(1 \le A, B, K \le 10^{10})$

출력 형식

VITAS가 조건을 만족시키면서 초대할 수 있는 지구인의 수의 최댓값을 출력한다.

예제 입력 1

3 9 1

예제 출력 1

4

예제 입력 2

5 10 3

예제 출력 2

5

예제 입력 3

7 8 7

예제 출력 3

15

힌트

<iframe allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="315" src="/media/problems/30390/1.png" width="560"></iframe>