У вас есть плитка шоколада, состоящая из n × m долек. Вы хотите съесть ровно k долек, для этого может потребоваться разделить шоколадку на части.
За одно действие можно разломить ровно один цельный прямоугольный кусок шоколада на два прямоугольных куска. Разламывать можно только по линиям, проходящим между дольками: по горизонтали или по вертикали. Стоимость разлома равна квадрату длины разлома.
Например, если сначала у вас была шоколадка из 2 × 3 долек, то за один горизонтальный разлом вы можете получить два цельных куска 1 × 3 (стоимость такого разлома равна 32 = 9), либо вы можете разломить шоколадку по вертикали одним из двух способов и получить два цельных куска 2 × 1, 2 × 2 (стоимость такого разлома равна 22 = 4).
Ваша задача для нескольких значений n, m и k определить, за какую минимальную суммарную стоимость разломов, можно разделить исходную шоколадку на такие прямоугольные куски, что можно выбрать несколько кусков, суммарный размер которых составляет ровно k долек. При этом оставшиеся n·m - k долек не обязательно образуют цельный кусок.
Выходные данные
Для каждой тройки n, m и k выведите минимальную стоимость, которую необходимо потратить на разламывание шоколадки, чтобы можно было съесть ровно k долек.
Примечание
В первом запросе из примера необходимо сделать два разлома:
- сначала нужно разбить кусок размера 2 × 2 на два куска размера 2 × 1 (стоимость такого разлома равна 22 = 4),
- затем нужно один из получившихся кусков размера 2 × 1 разломить на два куска размера 1 × 1 (стоимость такого разлома равна 12 = 1).
Во втором запросе из примера вы хотите съесть 3 дольки. Для этого можно действовать аналогично первому запросу.