시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB250837336.318%

문제

W×H 크기의 종이가 있다. 지금 현정이가 필요한 종이의 크기는 넓이가 A인 종이이다. 따라서, 종이를 접어서 넓이가 A인 종이를 만들려고 한다.

종이는 직선을 기준으로 접어야하며, 다음과 같은 두 가지 조건을 지켜야 한다.

  • 종이를 접는 기준선은 직사각형의 한 변과 평행해야 한다.
  • 종이를 접은 후에도 W와 H는 정수가 되어야 한다.

예를 들어, 5×3 크기의 종이가 있는 경우에, 너비를 기준으로 4가 되는 선으로 종이를 접으면 4×3 크기의 종이를 접게 된다. 이제, 높이를 기준으로 1이 되는 선을 기준으로 종이를 접어서 5×2 크기의 직사각형을 만들 수 있다.

W, H, A가 주어졌을 때, 넓이가 A가 되게 접을 수 있는지 없는지 구하고, 접을 수 있는 경우에는 접어야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 W, H, A가 주어진다. (1 ≤ W, H ≤ 1,000,000,000, 1 ≤ A ≤ 100,000)

출력

W×H 크기의 종이를 접어서 넓이가 A가 되게 만들 수 있으면 접는 횟수의 최솟값을, 만들 수 없으면 -1을 출력한다.

예제 입력 1

5 3 12

예제 출력 1

1

예제 입력 2

2 2 3

예제 출력 2

-1

예제 입력 3

4 4 1

예제 출력 3

4

예제 입력 4

127 129 72

예제 출력 4

8

예제 입력 5

1 100000 100000

예제 출력 5

0

예제 입력 6

1 1 2

예제 출력 6

-1

출처