BCAKE  Birthday Cake
Today is the birthday of Seraph. Kasumi as his best friend want to give a surprice to Seraph, she know that Seraph love to eat chocolate cake, unfortunately Seraph should not be too much to eat chocochip, the maximum he can only take K chocochip in the cake and he want the cake that he'll eat is rectangle. If Seraph can't get K chocochip or not rectangle then he don't want eat that cake.
You'll give the configuration of the cake, then please help Kasumi to know minimum area of that cake that Seraph can eat.
Input
first line is test case, then each test case will contain H (1 ≤ H ≤ 30), W (1 ≤ W ≤ 30), K (0 ≤ K ≤ 900) that means H is the height of cake, W is width of cake and K is maximum chocochip that seraph can eat.
on the next line you'll give the configuration of the cake where 'C' means chocochip area and '.' is normal cake area. You can assume that width and height of cake between 1 and 30 inclusive.
Output
Print one line A that means the minimum area that seraph can eat. If Seraph can't eat that cake then print '1'
Example
Sample Input 1: 1
5 6 4 ...... .C.... ..CC.. ...CC. ...... Sample Output 1:
6
Sample Input 2: 1
5 6 3 ...... ...... ..CC.. ..CC.. ...... Sample Output 2: 1
hide comments
rising_stark:
20200501 12:12:44
Well I got an AC with ans=1 for k=0


rising_stark:
20200430 08:54:58
Is it always the case with SPOJ questions that the problem description is always bad and confusing.


whyamievenhere:
20190403 17:28:47
Pathetic English. 

blagojce:
20180721 00:32:25
Is there any O(w * h) time solution, because i cant think better solution then O(min(w *w * h, h * h * w))?


mag1x_:
20180701 07:33:46
O(h*h*w*w) :p 

Amitayush Thakur:
20180614 17:01:56
Did not use DP, simple brute force (O(H^2 * W^2)) passed with 0.00!! Test cases are weak. 

Sigma Kappa:
20170528 21:10:52
Very disappointing, got Accepted with O(n^4) standard DP. Maybe the constraints for H, W should be higher to force us to think about a maxflow approach. What is the original TopCoder description and link? 

trojanworm:
20160908 14:28:04
Why is this in maxflow? Can someone please help me with a maxflow solution? Thanks 

theph0enix:
20160708 08:52:55
For k=0, answer should be 1. Since the man can eat any unit area without 'C' on it. AC 0.0! :) 

NoszĂˇly Csaba:
20111223 17:56:03
@Fendy: a little bit confusing the case K=0. One of my submissions, got ac, however it gives 0 for the input below:

Added by:  [Retired] Fendy Kosnatha 
Date:  20111201 
Time limit:  0.100s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  inspired by TopCoder problem 