LAZYCOWS  Lazy Cows
English  Vietnamese 
Farmer John regrets having applied highgrade fertilizer to his pastures since the grass now grows so quickly that his cows no longer need to move around when they graze. As a result, the cows have grown quite large and lazy... and winter is approaching.
Farmer John wants to build a set of barns to provide shelter for his immobile cows and believes that he needs to build his barns around the cows based on their current locations since they won't walk to a barn, no matter how close or comfortable.
The cows' grazing pasture is represented by a 2 x B (1 <= B <= 15,000,000) array of cells, some of which contain a cow and some of which are empty. N (1 <= N <= 1000) cows occupy the cells in this pasture:
   cow     cow  cow  cow  cow     cow  cow  cow       
Ever the frugal agrarian, Farmer John would like to build a set of just K (1 <= K <= N) rectangular barns (oriented with walls parallel to the pasture's edges) whose total area covers the minimum possible number of cells. Each barn covers a rectangular group of cells in their entirety, and no two barns may overlap. Of course, the barns must cover all of the cells containing cows.
By way of example, in the picture above if K=2 then the optimal solution contains a 2x3 barn and a 1x4 barn and covers a total of 10 units of area.
Input
The first line of the input contains integer t representing the number of test cases. Then t cases follow. Each case has the following form:
 Line 1: Three spaceseparated integers, N, K, and B.
 Lines 2..N+1: Two spaceseparated integers in the range (1,1) to (2,B) giving the coordinates of the cell containing each cow. No cell contains more than one cow.
Output
For each test case, output the minimum area required by the K barns in order to cover all of the cows.
Example
Input: 1 8 2 9 1 2 1 6 1 7 1 8 1 9 2 2 2 3 2 4 Output: 10Input details: As pictured above.
Output details: As discussed above.
hide comments
Sumit Paroothi:
20160321 01:02:04
one hell of a question!!! 

paras meena:
20141003 06:42:50
Nice one :) took 1 day :( bt anyway AC :D 

farzad abdolhoseini:
20120728 11:56:29
should he build all of the k barns?


Daniel Ferizovic:
20100101 18:15:13
I think the answer in your test case should be 2. Cause you can build 2 barns. So there will be two barns of a 1x1 rectangle, one for each cow. Last edit: 20100101 20:55:32 

David Gómez:
20091231 20:43:37
1


Ahmed Kamel [ahm.kam_92]:
20091220 19:20:18
Nice problem :) 
Added by:  Duc 
Date:  20050503 
Time limit:  9s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  US Open International 2005 Gold Division 