Задача: Деление шоколадки

У Маши есть прямоугольная шоколадка, состоящая из m × n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки. У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске.

Формат входных данных
Программа получает на вход три натуральных числа, каждое в отдельной строке: m, n и k. Все числа — целые положительные, при этом m и n не превосходят 10⁶ , а k ≤ mn.
Обратите внимание на то, что значение mn, а, значит, и значение k в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Программа должна вывести одно целое число — максимально возможное количество долек в том прямоугольном куске, который получит Юра.

Замечание
В примере из условия нужно разделить шоколадку 4 × 5 на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке.
 

Ваш ответ: