1228 - Chocolate

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / Writer ei1903 / x 3 / 統計 /


TLE
1sec
MLE
64MB
得点
100

問題

H ピース、横 W ピースでできた一枚のチョコレートがある。(ピースは全て同じ大きさの正方形)
あなたはこのチョコレートを何回か切って N ピースでできた一枚のチョコレートにしたいと考えている。
何回切ることで N ピースでできた一枚のチョコレートにすることができるだろうか。切る最小の回数を出力せよ。
ただし、切る際には以下のルールがある。

  • 切るときにはピースの境目に沿って縦一直線、又は横一直線にしか切ることは出来ない。
  • 一回も切らなくてもよい。
  • 切り終わった N ピースでできたチョコレートは長方形でなくてはいけない。

入力

H W N

出力

最小で何回切ることで条件を満たすチョコレートにすることができるか出力せよ。
また、何回切っても条件を満たすチョコレートにすることができない場合は-1と出力せよ。
出力の末尾には改行を入れること。

制約

  • 1 ≤ H,W ≤ 106
  • 1 ≤ N ≤ 1012

小課題

1.(30点)
  • 1 ≤ H,W ≤ 103
  • 1 ≤ N ≤ 106
2.(70点) 追加の制約はない。

入出力例

例1

入力

2 4 3

出力

2

解説
1回目:縦,2回目:横と、以下のように赤い線で切ればよい。

例2

入力

2 3 5

出力

-1

例3

入力

3 3 9

出力

0