3153. I-country

【题目描述】

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

求出这个最大的权值和，并给出连通块的具体方案。

【输入格式】

在输入的第一行有3个整数$n，m，k(1\leq n,m\leq 15,0\leq k\leq n\times m)$。

接下来的$n$行包含$m$个整数，即每个格子的权值(范围在0到1000之间)。

【输出格式】

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

接下来$k$，每行两个整数表示凸连通块的格子的坐标，第一个坐标是行数(从上到下，从1开始)，第二个坐标是列数(从左到右，从1开始)。

如果存在多种方案，输入其中的任意一种。

【样例输入】

2 3 4
10 20 30
40 2 3

【样例输出】

Oil : 100
1 1
1 2
1 3
2 1

【来源】

《算法竞赛进阶指南》