#6675. 下棋

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

小 B 和小 S 准备参加学校最火爆的围棋社。

作为资格考试，社长给他们出了一道题：给出一个有 $n$ 条水平线与 $m$ 条竖直线构成的棋盘（并不一定是传统围棋棋盘的 $19$ 条线），然后他们有 $k$ 枚棋子可以摆放到棋盘上的网格的交叉点上。我们定义一个方案的「赢面」为棋盘上「四边与棋盘上的直线重合」且「四个角上都有棋子」的矩形个数。

小 B 和小 S 当然要尽量选出「赢面」最大的方案。不过他们还要学求导，背元素周期表，刷物理必刷题……所以他们向你求助。如果你成功帮助他们，就会得到巴蜀无限饭卡（不存在的）。

一行输入三个数 $n,m,k$ 。

一行一个整数表示能得到的最大「赢面」。

输入

3 3 8

输出

输入

7 14 86

输出

对于 $50\%$ 的数据， $0<N,M\le 30$ ；
对于 $100\%$ 的数据， $0<N,M\le 3\times 10^4,K\le N\times M$ 。