Maximizing Axis-Parallel Rectangles

Given a grid formed by \(N\) horizontal lines and \(M\) vertical lines, there are \(N\times M\) intersection points. You are allowed to place \(K\) stones on distinct intersection points. The goal is to choose a placement of stones such that the number of axis-parallel rectangles (with sides parallel to the coordinate axes) whose four vertices each contain a stone is maximized.

A rectangle is defined by selecting two distinct horizontal lines and two distinct vertical lines. If stones are placed on all intersections of the chosen lines, a rectangle is formed. The count of rectangles in a fully filled \(r\times c\) subgrid is given in \(\LaTeX\) by:

[ \binom{r}{2}\times\binom{c}{2} = \frac{r(r-1)}{2}\times\frac{c(c-1)}{2} = \frac{r(r-1)c(c-1)}{4} ]

Your task is to pick integers \(r\) and \(c\) such that \(2\le r\le N\), \(2\le c\le M\) and \(r\times c \le K\) in order to maximize the number of rectangles. Note that if \(K\) is at least \(N\times M\), you can use all intersection points and the answer will be:

[ \binom{N}{2}\times\binom{M}{2} = \frac{N(N-1)M(M-1)}{4} ]

If it is impossible to place stones to form any rectangle (for example, when \(K < 4\)), the result is 0.

inputFormat

The input consists of a single line containing three space-separated integers \(N\), \(M\), and \(K\) where:

• \(N\) is the number of horizontal lines.
• \(M\) is the number of vertical lines.
• \(K\) is the number of stones available.

outputFormat

Output a single integer, the maximum number of axis-parallel rectangles that can be formed such that each of the rectangle's four vertices has a stone.

sample

4 4 4

1