Description

Stanko works as an architect in a construction company. His current task is to design a floor plan for a residential building in Zagreb. He must find a way to partition the floor into rectangular apartments using walls. Each wall must be parallel to the sides of the building. More precisely, the floor is represented in the plan as one large rectangle of size $n\times m$, and each apartment is a smaller rectangle of size $a\times b$ inside the large rectangle. The numbers $a$ and $b$ must be integers.

In addition, the floor must be completely covered by apartments: every point of the floor must lie inside some apartment. Apartments must not overlap, but they may touch.

To prevent the rooms from being dark, each apartment must have a window. Therefore, each apartment must have one side that lies on the boundary of the rectangle representing the floor, so that a window can be placed.

Also, the area of all apartments should be close to $k$. The deviation of an apartment of size $a\times b$ is defined as $(a\times b-k)^2$. The deviation of a floor plan is the sum of the deviations of all apartments.

Stanko wants to build the best building he can, i.e. a building with the minimum deviation. Help him by writing a program that determines the minimum possible deviation of a floor plan that satisfies all the conditions.

Input Format

A single line contains three integers $n,m,k$.

Output Format

One line: the minimum possible deviation of an apartment layout.

3 3 2

1

2 2 2

0

2 3 4

2

Hint

Explanation of Sample 1

This sample corresponds to the left picture in the statement. Note that it is impossible to achieve a deviation of $0$.

Constraints

For $100\%$ of the testdata, $1\le n,m\le 300$, $1\le k\le 10^4$.

Note

This problem is translated from COCI2014-2015 CONTEST #4 T6 STANOVI.

Translated by ChatGPT 5