Optimal Apartment Partitioning

Stanko is an architect working for a construction company. His current task is to design a floor plan for a residential building in Zagreb. The floor is represented as a large rectangle of dimensions \(n \times m\). He must partition the floor into apartments by placing walls that are parallel to the sides of the floor. Each apartment must be a smaller rectangle with integer dimensions \(a \times b\) that lies completely inside the floor.

The partition must cover the entire floor without overlapping apartments (although they may touch). In order to ensure ample natural light, every apartment must have at least one side on the boundary of the floor rectangle (so that a window can be installed).

In addition, all apartments are intended to have areas as close as possible to a target value \(k\). For an apartment of dimensions \(a \times b\), its area deviation is defined as \((a \times b - k)^2\). The total deviation of a floor plan is the sum of deviations over all apartments.

Help Stanko build the best building possible by computing the minimum total deviation among all valid floor plans that satisfy the above conditions.

Input Format: Three integers \(n\), \(m\), and \(k\) separated by spaces.

Note: Walls must always be parallel to the sides of the floor. In any valid partition, every apartment must have at least one edge on the boundary of the \(n \times m\) rectangle.

inputFormat

The input consists of a single line containing three space-separated integers:

(n) (m) (k)

where (n) and (m) are the dimensions of the floor, and (k) is the target area for each apartment.

outputFormat

Output a single integer — the minimum total deviation possible for a valid partitioning of the (n \times m) floor.

sample

3 3 4

3