Background

Our great KK suddenly came up with a very clever problem.

Problem Description

In a grid formed by $N$ horizontal lines and $M$ vertical lines (KK's self-made coordinate system), KK places $K$ stones, each stone only allowed to be placed at an intersection point of the grid.

Now KK wants to know, under the optimal placement, the maximum number of rectangles whose sides are parallel to the coordinate axes, and he requires that each of the four vertices of such a rectangle has exactly one stone placed on it.

Input Format

One line with three integers $N, M, K$.

Output Format

Output one integer on a single line, representing the maximum number of rectangles that meet the requirement.

3 3 8

5

Hint

Constraints:

• For $50\%$ of the testdata, $N, M \le 30$.
• For $100\%$ of the testdata, $1 \le N, M \le 3 \times 10^4$, $0 \le K \le N \times M$.

Translated by ChatGPT 5