Oil on the Mars

According to top-secret mars sensor transition, a big oil field was founded on the Mars. The field is divided into N*M equal square, and each square contains some oil resources. Our army want to occupy all the territory of the field, but the UN (United Nations) will allow us to occupy only K squares. Of course, we want to get control over as many oil as possible, but, we will have to guard all our territory. So, they need our 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 determines, how many oil will be occupied by us.

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

One line for a case, write string "Oil : X", where integer number X --- the maximal number of oil which can be controlled.

2 3 4 
10 20 30 
40 2 3

Oil : 100 

2009 Multi-University Training Contest 5 - Host by NUDT