창고의 공용 상자 규격

문제

물류 창고에는 두 종류의 부품이 각각 A개와 B개 있다. 창고 관리자는 두 종류의 부품을 모두 상자에 담으려고 한다. 부품의 종류가 다르면 서로 다른 상자를 사용하며, 하나의 상자에 두 종류의 부품을 섞어 담을 수 없다. 다만 상자를 주문하고 쌓는 작업을 단순하게 만들기 위해 모든 상자에는 같은 개수의 부품을 넣기로 했다. 상자 하나에 넣는 부품의 개수를 규격이라고 부른다. 규격은 양의 정수여야 하며, 작업대의 크기 때문에 K 이하여야 한다. 선택한 규격이 d라면 첫 번째 종류의 부품을 담는 모든 상자에 정확히 d개씩 넣고, 두 번째 종류의 부품을 담는 모든 상자에도 정확히 d개씩 넣는다. 어느 종류에서도 부품이 남아서는 안 되며, 일부만 채운 상자를 따로 만들거나 빈 공간을 완충재로 채우는 것도 허용하지 않는다. 예를 들어 부품이 각각 18개와 30개이고 규격의 상한이 5라면, 규격 3은 두 종류를 모두 남김없이 담을 수 있으므로 사용할 수 있다. 규격 5는 첫 번째 종류의 부품이 남으므로 사용할 수 없다. 규격 6은 두 종류의 부품 수를 모두 나눌 수 있지만 상한을 넘으므로 사용할 수 없다. 관리자는 사용할 상자의 수를 줄이기 위해 조건을 만족하는 규격 중 가장 큰 값을 선택한다. A, B, K가 주어질 때 관리자가 선택할 규격을 구하는 프로그램을 작성한다. 두 부품 수는 모두 양수이고 규격 1은 항상 사용할 수 있으므로 답이 없는 경우는 발생하지 않는다. 같은 최댓값을 갖는 서로 다른 규격도 없으므로 동점 처리는 필요하지 않다.

입력

첫째 줄에 정수 A, B, K가 공백으로 구분되어 주어진다.
1 ≤ A, B, K ≤ 1,000이다.

출력

조건을 만족하는 가장 큰 규격을 정수 하나로 출력한다.

18 30 5

3

24 36 20

12

7 11 1

1

출처: Devin.KR 자체 제작