DEFKIN2  Defense of a kingdom 2
This is an extension to the problem DEFKIN http://www.spoj.com/problems/DEFKIN/ and solve it first before doing this.
Theodore implements a new strategy game “Defense of a Kingdom”. On each level a player defends the Kingdom that is represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. The tower defends all the cells in the same row and the same column. No two towers share a row or a column.
Now the king inputs width(w),height(h),number of towers(n). Here n<= min(w,h).
There there can be many ways to place the towers in the grid.
Lets define a function penalty(N_{i}) for the ith combination of tower placements,which is number of cells in the largest undefended rectangle. For example,one of the combinations of placing a tower is shown in the picture and has a penalty=12.
Suppose there are in total k combinations . Then there are penalty(N_{1}),penalty(N_{2}),penalty(N_{3})...........penalty(N_{k}).
The task of the user is to find the minimum of these penalties.
Input
The first line of the input file contains the number of test cases.
Each test case consists of a line with three integer numbers: w — width of the grid, h — height of the grid and n — number of crossbow towers (1 ≤ w, h ≤ 40 000; 0 ≤ n ≤ min(w, h)).
Output
For each test case, output a single integer number the minimum penalty
Output answer for each test case in a new line
Example
Input: 1
15 8 3
Output: 6
hide comments
vivu01:
20160308 15:45:30
Last edit: 20160308 16:28:50 

Narendra pal:
20151024 19:04:27
how come the output is 6....can anyone explain....


agspoj:
20151006 16:43:12
I have removed Scanner and used bare System.in, and that solved the problem. 

mehmetin:
20151006 13:54:36
@agspoj: You should use a faster input method. 

agspoj:
20151006 12:02:44
I got time limit exceeded although my code involves only reading and parsing input and calculating one simple equation. It cannot be done faster in java.


mehmetin:
20151004 12:34:39
Actually an easy problem. I got lots of wrong answers before getting accepted, due to wrong approach. 

mandrathax:
20151003 11:24:51
I think there is a typo under output, one should output the *minimum* penalty obviously 

snehil10111995:
20150928 19:35:22
No link to submit the problem

Added by:  Neel 
Date:  20150928 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 