K명의 친구들이 영화를 보러 간다. 하지만 너무 늦게 온 바람에 좋은 자리의 티켓들은 거의 다 팔려버린 상태였다. 그들은 서로 가까운 자리에 앉으려고 한다. 그들을 도와주자.

영화관은 R 개의 줄과 각 줄당 C개의 좌석 있다. 즉 R x C 행렬로 생각해도 좋다.

이 중 몇 개의 좌석은 이미 티켓이 팔려서 앉을 수가 없다. 모든 친구들이 다 앉을 수 있는 크기 r x c 인 사각형 (r x c 소 행렬) 의 최소 넓이/크기를 구하는 게 문제이다.

입력

• 입력의 첫 줄은 정수 R, C, K 가 공백을 사이로 주어진다. (1<=R,C<=300, 1<=K<=R^C)
• 다음 R줄은 각각 길이 C인 문자열이 주어진다. i번째 줄에 j번째 문자가 ‘.’ 이면 비어있단 뜻이고 ‘X’이면 그 자리는 이미 팔려버린 상태란 것이다. 입력에서 적어도 K개의 자리는 비어있다.

출력

입출력 예

입력

3 5 5
...XX
.X.XX
XX...

출력 

6

출처:ACM ICPC Southern Regional 2007
추천:likepad