JOCHEF - Farmer Sepp


Chief Farmer Josef aka Sepp needs to crop hay several times through the summer. Due to high petrol costs he can currently use his truck only once to drive to a spot where he will harvest the dried grass. Lazy by nature, John does not want to harvest those parts of the field which contain cows, since this would involve too much energy. Furthermore, John just crops a rectangular part of the field.

Input

Input contains multiple test cases. You are given three integers M, N, F (0 < M, N <= 4000), (0 <= F <= 1000000) which describe the size of the field (M rows, N columns, F unit area of such a field). Then follows the actual map which consists of M lines, each line containing N times the letters 'H' or 'C' standing for "Hay" or "Cow". Input terminates with M = N = 0.

Output

Print the size of the largest field, which "Sepp" would harvest.

Example

Input:
9 10 1
CHCHHHCCCC
CCHCHCHHHC
CCHCHHCCCC
CHHHHHCHHH
CHCHHHCCCH
CCCCHHHCHH
HHHCCHCCCC
HCHHHHCCCH
CHHCCCCHHC
0 0

Output:
8

hide comments
kesh4281: 2019-08-08 20:10:27

the significance of 'F' is... at the end we have to multiply our answer with it.

holmesherlock: 2018-06-09 14:37:35

can you please tell me ,,why I am getting TLE??
@Josef Ziegler:

Last edit: 2018-06-09 14:37:52
farhad chowdhury: 2016-04-19 05:26:56


no one helped but got ac thanks

Last edit: 2016-04-23 02:12:50
Rohan Anil: 2011-03-11 21:04:29

Woohooo!:D

Last edit: 2011-01-04 01:31:53
Jaros³aw Meller: 2010-07-02 22:39:13

@Josef Ziegler:
Thank You for Your answer - I managed to rewrite the code and after some fixes it works.. AC :-)...

Josef Ziegler: 2010-07-02 22:15:23

@ Jarosław Meller
I had a look at your submission #3787567, your program fails on simple cases such as
1 1 999999
H
0 0
Take a closer look at the 'unit area'...

Jaros³aw Meller: 2010-07-02 15:15:11

Keep getting WA while using same approach as in CTGAME problem... Any hints? Any tricky test data?


Added by:Josef Ziegler
Date:2010-04-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Josef Ziegler