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
Ahmed Kamel [ahm.kam_92]: 2011-12-05 19:38:30

So in case of K=0, the answer is?

Okay, I got accepted with answer=0 when K=0.

Last edit: 2011-12-05 20:05:53
Problem Solver: 2011-12-03 16:02:15

Description is truly hard to understand.

[Retired] Fendy Kosnatha: 2011-12-01 15:13:21

and i think your code will AC after you add the new template for input... :)

[Retired] Fendy Kosnatha: 2011-12-01 15:13:21

@ [Trichromatic] XilinX :
sorry for some silly mistakes in my TC. :D
and yes this is some modified problem from that..

[Rampage] Blue.Mary: 2011-12-01 15:13:21

OK. Few questions:
(i)Will The configuration be an rectangle?
(ii)If K=0, the answer is 0?
(iii)Are you sure your test cases are right?


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