CF390D Inna and Sweet Matrix

### 题目翻译 Inna非常喜欢甜食。这就是为什么她决定玩一个叫做“甜蜜矩阵”的游戏。 Inna看到了一个$ n×m $的矩阵和$ k $个糖果。我们将矩阵的行从$ 1 $到$ n $编号，矩阵的列从$ 1 $到$ m $编号。我们将第$ i $行和第$ j $列中的单元格表示为$ (i,j) $。如果$ |i-p|+|j-q|=1 $，则矩阵中的两个单元格$ (i,j) $和$ (p,q) $是相邻的。路径是矩阵单元格的序列，其中序列中每对相邻的单元格都是相邻的。我们将序列中的单元格数量称为路径的长度。 矩阵的每个单元格最多只能有一个糖果。最初，所有单元格都是空的。Inna正试图将每个糖果一个接一个地放入矩阵中。对于每个糖果，Inna选择包含糖果的单元格$ (i,j) $，还选择一条从单元格$ (1,1) $开始并结束于单元格$ (i,j) $的路径，且该路径不包含任何糖果。之后，Inna沿着路径将糖果从单元格$ (1,1) $移动到单元格$ (i,j) $，糖果将永远留在那里。如果在某个时刻Inna不能为糖果选择一条路径，则她输了。如果Inna能够以所述方式将所有糖果放入矩阵中，那么她的惩罚等于她所使用的所有路径的长度之和。 帮助Inna最小化游戏中的惩罚。

输入的第一行包含三个整数 $ n $，$ m $ 和 $ k $（$ 1\leq n,m \leq 50,1 \leq k \leq n·m $）。

在第一行打印一个整数——表示Inna在游戏中的最小惩罚。 在接下来的$ k $行中，打印每个糖果的路径描述。第$ i $个放置的糖果的路径描述应跟随在第$ i $行。路径的描述是一个单元格序列。每个单元格必须以格式$ (i,j) $写入，其中$ i $是行号，$ j $是列号。允许在行中打印额外的空格。如果存在多个最优解，则打印其中任何一个。

Note to the sample. Initially the matrix is empty. Then Inna follows her first path, the path penalty equals the number of cells in it — 3. Note that now no path can go through cell (2, 2), as it now contains a candy. The next two candies go to cells (1, 2) and (2, 1). Inna simply leaves the last candy at cell (1, 1), the path contains only this cell. The total penalty is: 3 + 2 + 2 + 1 = 8. Note that Inna couldn't use cell (1, 1) to place, for instance, the third candy as in this case she couldn't have made the path for the fourth candy.