#3399. I-区域 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

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

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

输入格式

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

接下来N行每行M个整数,表示N*M的矩阵上每个格子的权值(均不超过1000)。

输出格式

第一行输出“Oil : X”,其中X为最大权值和。

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

样例

样例输入

2 3 4 
10 20 30 
40 2 3

样例输出

Oil : 100 
1 1 
1 2 
1 3 
2 1

数据范围与提示

,