생산 라인의 공용 받침

문제

한 공장에는 서로 다른 부품을 만드는 두 생산 라인이 있다. 오늘 첫 번째 라인은 부품 A개를 만들었고, 두 번째 라인은 부품 B개를 만들었다. 공장은 두 라인에서 만든 부품을 각각 받침에 담아 다음 작업대로 옮기려 한다. 서로 다른 라인의 부품을 같은 받침에 섞어서 담지는 않는다. 창고에는 여러 크기의 받침이 있지만, 작업자가 받침을 쉽게 교체할 수 있도록 오늘은 한 가지 크기만 사용하기로 했다. 받침의 크기가 d라는 것은 받침 하나에 정확히 d개의 부품을 담는다는 뜻이다. 두 라인 모두 같은 크기 d를 사용해야 하며, 사용한 모든 받침에는 부품이 정확히 d개씩 들어 있어야 한다. 빈자리가 있는 받침을 보내거나 부품을 남겨 두는 것은 허용하지 않는다. 각 라인에서 사용하는 받침의 개수는 서로 달라도 된다. 예를 들어 한 라인의 생산량이 18개이면 크기 3인 받침 여섯 개에 모두 나누어 담을 수 있다. 하지만 크기 4인 받침을 사용하면 일부 부품이 남으므로 그 라인에는 사용할 수 없다. 두 라인이 함께 사용할 크기는 이와 같은 조건을 두 생산량에 모두 만족해야 한다. 또한 이동 장치의 설정 때문에 받침의 크기는 정수 K를 넘을 수 없다. 공장은 부품을 담는 횟수를 줄이기 위해 조건을 만족하는 크기 중 가장 큰 것을 선택하려 한다. 받침은 필요한 만큼 충분히 준비되어 있으며, 받침의 무게나 이동 순서는 고려하지 않는다. 생산량과 K는 모두 양의 정수이므로 크기 1인 받침은 언제나 사용할 수 있다. 두 생산 라인의 부품을 하나도 남기지 않고 나누어 담을 수 있는 공용 받침 크기의 최댓값을 구한다.

입력

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

출력

두 생산량 A와 B를 모두 나누어떨어지게 하면서 K 이하인 양의 정수 중 가장 큰 수를 출력한다. 조건을 만족하는 수는 항상 존재한다.

42 70 10

7

17 19 20

1

24 36 12

12

출처: Devin.KR 자체 제작