BCAKE - Birthday Cake


Today is the birthday of Seraph. Kasumi as his best friend want to give a surprise 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: 2020-05-01 12:12:44

Well I got an AC with ans=1 for k=0

But I seriously feel that the answer should have been 0 because to get 0 chocochips he doesn't need to eat the cake at all. So, 0 area of cake required.

Last edit: 2020-05-01 12:14:02
rising_stark: 2020-04-30 08:54:58

Is it always the case with SPOJ questions that the problem description is always bad and confusing.
I solved BAT4 before this and pulled my hair and now this one too.
Firstly the problem says that Seraph can take atmost K chocolate chips but then in the last line of first paragraph, it is said that "If Seraph can't get K chocochip", which I think means that exactly K chocochips but then while describing input, it is said that K is the maximum chocochips that Seraph can eat.

The sample input test case 2 is also set for exactly K chocochips.

I don't know what the problem is with this platform but its quality is degraded from earlier.

Last edit: 2020-04-30 08:56:03
whyamievenhere: 2019-04-03 17:28:47

Pathetic English.

blagojce: 2018-07-21 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_: 2018-07-01 07:33:46

O(h*h*w*w) :p

Amitayush Thakur: 2018-06-14 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: 2017-05-28 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: 2016-09-08 14:28:04

Why is this in max-flow? Can someone please help me with a max-flow solution? Thanks

theph0enix: 2016-07-08 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: 2011-12-23 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:
1
2 2 0
C.
CC
@Ahmed Kamel: are you sure? I send a solution which never outputs zero, and got AC :)



Last edit: 2011-12-23 18:02:34

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