우주왕자 사교파티

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

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

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

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

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