Finding Seats

Interview

Time limit1sMemory limit128 MB

Summary

Given an R by C grid of free and taken seats, place K people on free seats so the bounding rectangle has the smallest area.

Level: Medium6 of 10
Topics: Two pointers, Binary search, Prefix sum, Matrix
Solved: No attempts yet

Problem

A group of $K$ friends is going to the movies. They arrived too late to get good tickets, so they are looking for a good way to sit close together. Since they are all science students, they decided to turn the choice of seats into an optimization problem instead of arguing about which tickets to buy.

The theater has $R$ rows of $C$ seats each, and they can see a map marking the seats that are currently available. They care only about sitting close to one another, so they will buy seats that minimize the extension of their group.

The extension is defined as the area of the smallest rectangle, with sides parallel to the rows and columns, that contains all of the chosen seats. The area of a rectangle is the number of seats it contains. Given the map of available seats, find the minimum possible extension.

Input

The input consists of several test cases. Each test case begins with a line containing three positive integers $R$ , $C$ and $K$ ( $1 \le R, C \le 300$ , $1 \le K \le R \times C$ ). The next $R$ lines each contain exactly $C$ characters. The $j$ -th character of the $i$ -th line is X if that seat is taken, or . if it is available. Every test case has at least $K$ available seats in total.

The input is terminated by a line with $R = C = K = 0$ , which must not be processed.

Read the input from standard input.

Output

For each test case, print a single line containing the minimum extension the group can achieve.

Write the output to standard output.

Examples5

Example 1

Input

3 5 5
...XX
.X.XX
XX...
5 6 6
..X.X.
.XXX..
.XX.X.
.XXX.X
.XX.XX
0 0 0

Expected output

6
9

Example 2
Input
```
1 1 1
.
0 0 0
```
Expected output
```
1
```
Example 3
Input
```
2 3 1
.X.
XX.
0 0 0
```
Expected output
```
1
```
Example 4
Input
```
2 2 4
..
..
0 0 0
```
Expected output
```
4
```
Example 5
Input
```
1 5 3
.....
0 0 0
```
Expected output
```
3
```