Ai cũng biết rằng khi mèo chui vào các vật chứa rỗng, chúng thể hiện các đặc tính của chất lỏng.
Nhà toán học Petrov thường quan sát hiện tượng này qua những chú mèo của mình và thậm chí đã thực hiện một loạt thí nghiệm xây dựng các loại vật chứa khác nhau rồi đặt mèo vào đó. Hóa ra, mèo luôn chọn vị trí của chúng thấp nhất có thể, chính xác hơn là để giảm thiểu mức độ của điểm cao nhất trên cơ thể chúng. Trong trường hợp vật chứa có nhiều hố, mèo sẽ chọn hố thấp nhất nhưng chỉ trong số những hố mà chúng có thể vừa.
Một ý tưởng tuyệt vời đã nảy ra trong đầu Petrov: thực tế, mèo có thể được sử dụng như những máy tính tương tự để giải quyết một số bài toán tối ưu hóa lượng tử! Để kiểm tra giả thuyết của mình, nhà toán học Petrov đã phát triển mô hình toán học sau đây:
Hãy tưởng tượng một vật chứa là một bảng $T$ kích thước $n \times m$. Một số ô là tường, các ô còn lại là ô trống. Một cách đặt mèo trong vật chứa là tối ưu nếu thỏa mãn các điều kiện sau:
- Con mèo chiếm một số ô trống. Tất cả các ô mà con mèo chiếm giữ tạo thành một hình liên thông gồm $k$ ô. Một hình được gọi là liên thông nếu mỗi ô của nó có thể đi đến bất kỳ ô nào khác bằng cách di chuyển qua các ô kề cạnh (và tất cả các ô trung gian cũng phải được con mèo chiếm giữ).
- Mức độ của ô cao nhất $h$ mà con mèo chiếm giữ phải thấp nhất có thể. Các hàng của bảng được đánh số từ $1$ đến $n$ và một hàng được coi là cao hơn nếu số thứ tự của nó nhỏ hơn.
Thật không may, nhà toán học Petrov không giỏi lập trình. Ông ấy nhờ bạn xác định hàng chứa ô cao nhất $h$ mà con mèo chiếm giữ cho một bảng $T$ và thể tích con mèo $k$ cho trước.
Dữ liệu vào
Dòng đầu tiên chứa các số nguyên $n, m$ và $k$ ($1 \le n, m \le 1000, 1 \le k \le 10^6$).
$n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự — mô tả bảng $T$. Ký tự thứ $j$ của hàng thứ $i$ tương ứng với ô tại giao điểm của hàng thứ $i$ và cột thứ $j$ của $T$. “#” nghĩa là ô này là tường, và “.” nghĩa là ô này trống.
Dữ liệu ra
In ra số thứ tự của hàng chứa ô cao nhất mà con mèo chiếm giữ cho bất kỳ cách đặt mèo tối ưu nào. Nếu không thể đặt con mèo vào vật chứa, hãy in ra “-1” (không bao gồm dấu ngoặc kép).
Ví dụ
Ví dụ 1
6 11 7 ........... .......#... .......#... #......#... ########... #######..##
4
Ví dụ 2
6 11 15 ........... .......#... .......#... #......#... ########... #######..##
2
Ví dụ 3
5 11 30 ..#......## ........... ......#.... ......#.... ......#....
2
Ghi chú
Cách đặt mèo tối ưu cho mỗi ví dụ có thể như sau:
