같은 구성의 회의 공간

문제

한 사무실의 큰 회의실에는 등받이가 있는 의자 A개와 간이 의자 B개가 준비되어 있다. 직원은 이동식 칸막이를 설치하여 이 회의실을 여러 개의 작은 회의 공간으로 나누려고 한다. 각 공간의 넓이나 칸막이의 개수에는 제한이 없으며, 의자를 어떻게 나눌 수 있는지만 확인하면 된다. 회의 공간을 만들 때에는 두 종류의 의자를 모두 사용해야 한다. 창고에 남겨 두거나 회의실 밖으로 옮기는 의자가 있어서는 안 된다. 또한 모든 공간은 의자의 구성이 같아야 한다. 즉, 어느 공간을 선택하더라도 등받이가 있는 의자의 개수가 같아야 하고, 간이 의자의 개수도 같아야 한다. 한 공간에 놓는 두 종류의 의자 개수가 서로 같을 필요는 없다. 각 공간에는 두 종류의 의자가 각각 적어도 한 개씩 있어야 한다. 예를 들어 공간을 세 개 만든다면 등받이가 있는 의자를 세 공간에 똑같이 나눌 수 있어야 하며, 간이 의자도 세 공간에 똑같이 나눌 수 있어야 한다. 한 종류의 의자만 고르게 나누어지고 다른 종류의 의자가 남는 배치는 허용하지 않는다. 의자는 쪼개거나 여러 공간이 함께 사용하는 물건으로 취급할 수 없으므로 각 공간에 놓이는 개수는 모두 정수여야 한다. 직원은 이 규칙을 지키면서 가능한 한 많은 회의 공간을 만들려고 한다. 처음에 준비된 의자의 개수 A와 B가 주어질 때, 만들 수 있는 회의 공간 수의 최댓값을 구하라. 두 수는 모두 양의 정수이므로 전체 회의실을 하나의 공간으로 사용하는 배치는 항상 가능하다. 여러 배치가 같은 최대 공간 수를 만들더라도 배치 방법은 출력하지 않고 공간 수만 출력한다. 의자를 추가로 가져오거나 의자 종류를 바꾸는 일은 없다.

입력

첫째 줄에 두 종류의 의자 개수 A와 B가 공백으로 구분되어 주어진다.
A와 B는 정수이며, 1 ≤ A, B ≤ 1,000이다.

출력

조건을 만족하면서 만들 수 있는 회의 공간 수의 최댓값을 정수 하나로 출력한다.

24 36

12

7 11

1

18 18

18

출처: Devin.KR 자체 제작