在设计电路的过程中，常常要手动分析电路。

我们故事的主人公 —— 奸笑熊是一个参加了 NOI2015 结果遗憾退役的 OIer。

马上就要回班搞高考了，奸笑熊不免有点伤感。于是奸笑熊开始玩电路散散心。

奸笑熊的电路有 $n \times m$ 个节点，排成 $n$ 行 $m$ 列。任意两个相邻节点之间连着一条导线。如果两个节点 $(x_1, y_1), (x_2, y_2)$ 满足 $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert = 1$ 则称这两个节点相邻。

奸笑熊定义一个电路的复杂程度为最大的非负整数 $s$ 满足可以选出 $s$ 个节点使得任意两个被选中的节点间都有一根导线相连。

奸笑熊手里还有 $r$ 根导线，可以连在 $r$ 对节点之间。奸笑熊希望新加上不超过 $r$ 根导线后，电路的复杂程度最大。

请你帮奸笑熊手动分析他的电路，告诉他复杂程度最大是多少。

输入格式

共一行，包含三个整数 $n, m, r$。保证 $n, m \geq 1$，$r \geq 0$。

输出格式

共一行，包含一个整数表示答案。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

2 2 0

output

2

explanation

不能加导线。所以只能选择两个相邻的节点，复杂程度为 $2$。

样例二

input

2 3 3

output

4

限制与约定

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载