题目描述

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

输入格式

第一行包含三个整数$\red{N,M}$和$\red{K}$。 接下来$\red{N}$行每行$\red{M}$个整数，表示$\red{N\times M}$的矩阵上每个格子的权值（均不超过$\red{1000}$）。

输出格式

第一行输出“$\red{Oil : X}$”，其中$\red X$为最大权值和。

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

样例

输入样例

2 3 4 
10 20 30 
40 2 3

输出样例

Oil : 100 
1 1 
1 2 
1 3 
2 1

提示

$\red{1≤N,M≤15}$,

$\red{0≤K≤N\times M}$

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

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