P10972 I-Country

根据绝密的 A 国计划，I 国被划分为 $N\times M$ 个相等的正方形，每个正方形包含一些石油资源。他们希望占领整个 I 国的领土，但联合国只允许他们占领 $K$ 个正方形。 当然，A 国希望控制尽可能多的石油，但是他们必须守卫他们的全部领土。因此，他们需要他们的领土易于控制，即从任何一个正方形到另一个正方形只能沿着两个方向移动（从下列列表中选择：左、右、上、下；对于不同的正方形对，方向可能不同）。 你需要编写一个程序，确定 A 国将占领哪些正方形。如果有多个解决方案，你可以输出任意一个。

输入的第一行包含 3 个整数 $N$、$M$、$K$（$1≤N, M≤15$，$0≤K≤N\times M$）。 接下来的 $N$ 行包含每行 $M$ 个整数，表示该正方形上的石油资源数量。每个数字的范围在 $0$ 到 $1000$ 之间。

输出的第一行是字符串 Oil : X，其中 $X$ 是 A 国可以控制的最大石油数量。 接下来，你应该输出 $K$ 对数字，表示 A 国将占领的正方形的坐标。第一个坐标是行号（从上到下，从 $1$ 开始），第二个是列号（从左到右，从 $1$ 开始）。