Description

Ava 正在一个由格子组成的网格上玩策略游戏。每个格子都有一个对应的花费。当从左到右逐行读取格子的花费时，会呈现一个由前 $M$ 个正整数按递增顺序重复组成的模式：$1, 2, 3, \dots , M, 1, 2, 3, \dots , M, 1, 2, 3, \dots$。在这个模式中，$M$ 表示格子的最大花费。在示例网格中，$M$ 等于 $5$。

Ava 需要在每一行购买一个格子，以构建一条从上领地（第一行格子上方）通往下领地（最后一行格子下方）的连通路径。第一个购买的格子必须在第一行。随后购买的每个格子必须与上一个购买的格子共享一条边或一个角。在示例网格中，Ava 的连通路径总花费为 $9$。

给定一个格子网格，你的任务是确定从上领地到下领地的连通路径的最小花费。

Input Format

第一行输入一个正整数 $R$，表示网格的行数。第二行输入一个正整数 $C$，表示网格的列数。第三行输入一个正整数 $M$（$M \leq 100\,000$），表示格子的最大花费。

Output Format

输出一个正整数 $P$，表示连通路径的最小花费。

3
5
7

6

Hint

样例输入输出解释

每个格子的花费如图所示。Ava 应购买的格子序列（绿色高亮部分）使得连通路径的花费最小。

以下表格展示了 15 分的分配情况：

翻译由 DeepSeek V3 完成