| Codeforces Round 257 (Div. 1) |
|---|
| Закончено |
У Jzzhu есть большая прямоугольная плитка шоколада, которая состоит из n × m единичных квадратов. Он хочет разрезать плитку k раз. Каждый разрез должен удовлетворять следующим требованиям:
- каждый разрез должен быть прямолинейным (горизонтальным или вертикальным);
- каждый разрез должен проходить по границам единичных квадратов (запрещено разрезать единичные квадраты);
- каждый разрез должен проходить внутри всей шоколадной плитки, и все разрезы должны быть различными.
На рисунке снизу изображен один из способов разрезать шоколадку размера 5 × 6 пять раз.
Предположим, что Jzzhu уже сделал k разрезов, тогда большая шоколадка распалась на несколько кусков. Рассмотрим наименьший по площади кусок из получившихся. Jzzhu хочет, чтобы этот кусок был как можно больше. Какую максимальную возможную площадь наименьшего куска можно получить, сделав ровно k разрезов? Площадь куска шоколада считается равной количеству единичных квадратов внутри него.
В единственной строке записано три целых числа n, m, k (1 ≤ n, m ≤ 109; 1 ≤ k ≤ 2·109).
Выведите единственное целое число — ответ на задачу. Если не существует способа разрезать плитку ровно k раз, выведите -1.
3 4 1
6
6 4 2
8
2 3 4
-1
В первом примере Jzzhu может разрезать плитку, как показано на картинке внизу:
Во втором примере ответ выглядит так:
В третьем примере не существует способа разрезать плитку размера 2 × 3 четыре раза.
