No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 0.75 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

According to top-secret A-country plans, I-country is divided into N*M equal squares, each square contains some oil resources. They want to occupy all the territory of I-country, but the UN (United Nations) will allow them to occupy only K squares. Of course, A-country want to get control over as many oil as possible, but, they will have to guard all their territory. So, they need their territory to be easy-controlled, i.e. from any square to any it must be possible to get moving only along two directions (selected from the next list: left, right, up, down; for different squares pairs of directions may differ).

You are to write a program, which determinies, what squares will be occupyed by A-country. If there are several solutions, you may output any.

You are to write a program, which determinies, what squares will be occupyed by A-country. If there are several solutions, you may output any.

On the first line of input there are 3 integer numbers N,M,K (1<=N,M<=15, 0<=K<=N*M). Next N lines contains M integers each, which are the number of oil resource on that square. Each of this numbers lies in range of 0 to 1000.

On the first line of output, write string "Oil : X", where integer number X --- the maximal number of oil which can be controlled by A-country. Next you should output K pairs of numbers --- coordinates of the squares which will be occupied by A-country. The first coordinate is number of row (top to bottom, starting from 1), second is number of column (left to right, starting from 1).

Input

2 3 4

10 20 30

40 2 3

10 20 30

40 2 3

Output

Oil : 100

1 1

1 2

1 3

2 1

1 1

1 2

1 3

2 1

Author: | NNSU #2 team |

Resource: | |

Date: |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2021 13:43:18 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|