3153. I-country

【题目描述】

根据绝密的 A 国计划，I 国被划分为 $n\times m$ 个相等的正方形，每个正方形包含一些石油资源。他们希望占领整个 I 国的领土，但联合国只允许他们占领 $k$ 个正方形。

当然，A 国希望控制尽可能多的石油，但是他们必须守卫他们的全部领土。因此，他们需要他们的领土易于控制，即从任何一个正方形到另一个正方形只能沿着两个方向移动（从下列列表中选择：左、右、上、下；对于不同的正方形对，方向可能不同）。

你需要编写一个程序，确定 A 国将占领哪些正方形。如果有多个解决方案，你可以输出任意一个。

【输入格式】

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

接下来的$n$行包含$m$个整数，表示该正方形上的石油资源数量(范围在$0$到$1000$之间)。

【输出格式】

输出的第一行是字符串 Oil : x，其中 $x$ 是 A 国可以控制的最大石油数量。

接下来，你应该输出 $K$ 对数字，表示 A 国将占领的正方形的坐标。第一个坐标是行号（从上到下，从 $1$ 开始），第二个是列号（从左到右，从 $1$ 开始）。

【样例输入】

2 3 4
10 20 30
40 2 3

【样例输出】

Oil : 100
1 1
1 2
1 3
2 1

【来源】

《算法竞赛进阶指南》