Problem Description

According to the top-secret plan of Country A, Country I is divided into $N \times M$ equal squares, and each square contains some oil resources. They want to occupy the entire territory of Country I, but the United Nations only allows them to occupy $K$ squares.

Of course, Country A wants to control as much oil as possible, but they must defend all of their territory. Therefore, they need their territory to be easy to control, meaning that from any one square to any other square, you can move only along two directions (chosen from the following list: left, right, up, down; for different pairs of squares, the directions may be different).

You need to write a program to determine which squares Country A will occupy. If there are multiple solutions, you may output any one.

Input Format

The first line contains three integers $N$, $M$, and $K$ ($1 \le N, M \le 15$, $0 \le K \le N \times M$).

The next $N$ lines each contain $M$ integers, representing the amount of oil resources in each square. Each number ranges from $0$ to $1000$.

Output Format

The first line should be the string Oil : X, where $X$ is the maximum amount of oil that Country A can control.

Then, you should output $K$ pairs of numbers representing the coordinates of the squares that Country A will occupy. The first number is the row index (from top to bottom, starting from $1$), and the second is the column index (from left to right, starting from $1$).

2 3 4
10 20 30
40 2 3

Oil : 100
1 1
1 2
1 3
2 1

Hint

Translated by ChatGPT 5