P2180 Placing Stones

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

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.

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

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

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