167. Icountry.
time limit per test: 0.75
sec.
memory limit per test: 65536
KB
input: standard
output: standard
According to topsecret Acountry plans, Icountry is divided into N*M equal squares, each square contains some oil resources. They want to occupy all the territory of Icountry, but the UN (United Nations) will allow them to occupy only K squares. Of course, Acountry 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 easycontrolled, 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 Acountry. If there are several solutions, you may output any.
Input
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.
Output
On the first line of output, write string "Oil : X", where integer number X  the maximal number of oil which can be controlled by Acountry. Next you should output K pairs of numbers  coordinates of the squares which will be occupied by Acountry. The first coordinate is number of row (top to bottom, starting from 1), second is number of column (left to right, starting from 1).
Sample test(s)
Input
2 3 4
10 20 30
40 2 3
Output
Oil : 100
1 1
1 2
1 3
2 1
Author:  NNSU #2 team

Resource:  
Date:  
Server time: 20171121 16:50:34  Online Contester Team © 2002  2016. All rights reserved. 

