Apartment floor plan

Time limit2sMemory limit64 MB

Summary

Cover an N by M floor with integer-sided rectangles that each touch the outer edge so the sum of squared area deviations from K is minimal.

Level: Medium7 of 10
Topics: Dynamic programming, Divide and conquer, Geometry
Solved: No attempts yet

Problem

Stanko works as an architect at a construction company. His current task is the ground plan of one floor of a residential building. He has to split the floor with walls so that every apartment is a rectangle, and every wall he builds is parallel to a side of the building.

In the ground plan the floor is a large rectangle of size $N \times M$ , and an apartment is a smaller rectangle of size $a \times b$ placed inside it. The numbers $a$ and $b$ are integers.

The apartments have to cover the floor completely, so every point of the floor belongs to some apartment. Two apartments must not overlap, but they may touch.

Rooms must not be dark, so every apartment needs a window. Therefore each apartment has to keep part of one of its sides on an edge of the rectangle that represents the floor, and the window goes there.

The apartments also have to have area close to $K$ . The deviation of an apartment of size $a \times b$ is $(ab - K)^2$ , and the deviation of a ground plan is the sum of the deviations of its apartments.

Stanko wants to build the plan with the smallest deviation. Write a program that computes the smallest possible deviation of a ground plan that satisfies the conditions above.

Input

The first and only line contains the integers $N$ , $M$ , $K$ ( $1 \le N, M \le 300$ , $1 \le K \le 10000$ ), separated by spaces.

Output

Print the smallest possible deviation of a ground plan on a single line.

Examples4

Example 1
Input
```
3 3 2
```
Expected output
```
1
```
Example 2
Input
```
2 2 2
```
Expected output
```
0
```
Example 3
Input
```
2 3 4
```
Expected output
```
2
```
Example 4
Input
```
1 1 1
```
Expected output
```
0
```