Jzzhu 有一个大的矩形巧克力棒,由 n × m 个单位正方形组成。他想把这个条正好切 k 次。每次切割必须满足以下要求:
- 每次切割都应该是直的(水平或垂直);
- 每次切割应沿着单位方块的边缘(禁止用切割分割任何单位巧克力方块);
- 每个切口都应进入整个巧克力棒,并且所有切口必须清晰。
下图展示了将 5 × 6 巧克力切割 5 次的可能方法。
想象一下,Jzzhu 做了 k 次切割,大巧克力被分成几块。考虑最小(按面积)的巧克力块,Jzzhu 希望这块巧克力尽可能大。通过恰好 k 次切割,他能得到的最小块的最大可能面积是多少?巧克力块的面积是其中单位正方形的数量。
输入
单行包含三个整数 n、m、k (1 ≤ n, m ≤ 109; 1 ≤ k ≤ 2·109)。
输出
输出代表答案的单个整数。如果不可能将大巧克力切k次,则打印-1。
示例
输入 #1
3 4 1
输出 #1
6
输入 #2
6 4 2
输出 #2
8
输入 #3
2 3 4
输出 #3
-1
注意
在第一个示例中,Jzzhu 可以按照下图切割巧克力:
在第二个示例中,最佳划分如下所示:
在第三个示例中,不可能将 2 × 3 巧克力切割 4 次。