У Маши есть прямоугольная шоколадка, состоящая из $$$m\times n$$$ квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на $$$k$$$ кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки.
У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске.
Программа получает на вход три натуральных числа, каждое в отдельной строке: $$$m$$$, $$$n$$$ и $$$k$$$. Все числа — целые положительные, при этом $$$m$$$ и $$$n$$$ не превосходят $$$10^6$$$, а $$$k\le mn$$$.
Обратите внимание на то, что значение $$$mn$$$, а, значит, и значение $$$k$$$ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Программа должна вывести одно целое число — максимально возможное количество долек в том прямоугольном куске, который получит Юра.
Решения, правильно работающие при $$$m\le 1000$$$ и $$$n\le 1000$$$, будут оцениваться в 60 баллов.
454
16
В примере из условия нужно разделить шоколадку $$$4\times 5$$$ на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке.
