우편 봉투의 묶음 크기

문제

한 우체국의 작업대에 파란 우편 봉투 A개와 노란 우편 봉투 B개가 놓여 있다. 담당자는 보관함에 넣기 전에 봉투를 일정한 크기의 묶음으로 만들려고 한다. 파란 봉투끼리만 묶고 노란 봉투끼리만 묶어야 하며, 서로 다른 색의 봉투를 한 묶음에 섞을 수는 없다. 두 색에 사용하는 묶음 크기는 같아야 한다. 묶음 크기를 d로 정하면 모든 묶음에는 정확히 d개의 봉투가 들어간다. 각 색의 봉투를 전부 묶은 뒤 남는 봉투가 없어야 하므로 A와 B는 모두 d로 나누어떨어져야 한다. 일부 봉투를 따로 보관하거나 다른 작업대에서 봉투를 가져오는 일은 허용하지 않는다. 봉투의 순서는 구분하지 않으며, 묶음을 만드는 순서도 결과에 영향을 주지 않는다. 보관함의 한 칸에는 봉투를 최대 L개까지 넣을 수 있다. 각 묶음을 한 칸에 넣어야 하므로 묶음 크기 d는 L 이하여야 한다. L은 한 묶음에 들어가는 봉투 수의 상한이며, 만들 수 있는 전체 묶음 수의 상한은 아니다. 사용할 수 있는 보관함의 칸 수는 충분하다. 담당자는 이 조건들을 모두 지키면서 한 묶음에 들어가는 봉투 수를 가능한 한 크게 정하려 한다. A, B, L이 주어졌을 때 선택할 묶음 크기를 구하는 프로그램을 작성한다. 세 입력값과 묶음 크기는 모두 양의 정수다. 크기가 1인 묶음은 언제나 만들 수 있으므로 조건을 만족하는 답이 없는 경우는 없다. 출력해야 하는 값은 만들어지는 묶음의 개수가 아니라 한 묶음에 들어가는 봉투의 개수다. 가능한 크기 중 가장 큰 정수 하나를 출력하므로 별도의 동점 처리도 필요하지 않다.

입력

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

출력

두 색의 봉투를 남김없이 묶을 수 있고 L 이하인 묶음 크기 중 가장 큰 값을 한 줄에 출력한다.

24 36 5

4

17 25 10

1

18 30 100

6

출처: Devin.KR 자체 제작