题目描述

在 $N \times M$ 的矩阵中，每个格子有一个权值，要求寻找一个包含 $K$ 个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的），使这个连通块中的格子的权值和最大。

注意：凸连通块是指：连续的若干行，每行的左端点列号先递减、后递增，右端点列号先递增、后递减。（递增、递减都是非严格的）

求出这个最大的权值和，并给出连通块的具体方案，输出任意一种方案即可。

输入格式

第一行包含三个整数 $N,M$ 和 $K$。

接下来 $N$ 行每行 $M$ 个非负整数，表示 $N \times M$ 的矩阵上每个格子的权值（均不超过 $1000$）。

输出格式

第一行输出 Oil : X，其中 $X$ 为最大权值和。

接下来 $K$ 行每行两个整数 $x_i$ 和 $y_i$，用来描述所有格子的具体位置，每个格子位于第 $x_i$ 行，第 $y_i$ 列。

样例

输入样例：

2 3 4 
10 20 30 
40 2 3

输出样例：

Oil : 100 
1 1 
1 2 
1 3 
2 1

样例解释

矩阵：

10 20 30
40  2  3

$K=4$，需要选 4 个格子的凸连通块。

一种凸连通块：选择第一行全部（3 个格子）和第二行第一列（1 个格子），权值和 $10+20+30+40=100$，这是最大可能值。

方案输出这 4 个格子的坐标。

数据范围

• $1 \le N, M \le 15$
• $0 \le K \le N \times M$

时空限制

• 时间限制：2 秒
• 空间限制：256 MB