← 返回题目列表

Codeforces · 449/A

A. Jzzhu和巧克力

中文机器翻译题面 查看原题

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 次。