Chọn quà

Để khích lệ học sinh tích cực học tập, cô giáo lớp An dùng các nhãn dán khen thưởng khi tổ chức các hoạt động trên lớp. Cuối năm, cô khen thưởng cho các bạn tích lũy được nhiều nhãn. Với sự nỗ lực, An đã tích lũy được $K$ nhãn.

Cô chuẩn bị một khung lưới hình chữ nhật có kích thước $D \times R$. Khung lưới này có $D$ đường ngang và $R$ đường dọc tạo thành $(D-1) \times (R-1)$ hình vuông nhỏ có chiều dài cạnh là 1 đơn vị. Các món quà được treo tại các mối nối giao nhau của những đường ngang và đường dọc trên lưới. Tại một mối nối có thể không có quà hoặc có nhiều nhất một món quà.

Để nhận quà, An được phát cho một khung vợt hình vuông có kích thước $K \times K$ (cách tính đơn vị như khung lưới). An đặt vợt trên khung lưới sao cho 4 cạnh của vợt phải nằm hoàn toàn trên các đường ngang, đường dọc của khung lưới. Khi đó An sẽ nhận các món quà nằm hoàn toàn bên trong 4 cạnh của vợt (các món quà nằm trên cạnh của vợt sẽ không được tính). Bạn hãy giúp An xác định số lượng lớn nhất các món quà mà An có thể nhận.

Yêu cầu: Viết chương trình cho biết số lượng món quà lớn nhất mà An có thể nhận khi đặt vợt trên khung lưới.

Vào từ tập tin văn bản CHONQUA.INP, gồm:

• Dòng đầu tiên chứa 3 số nguyên $D, R, K$ $(3 \le K \le D, R \le 1000)$ cách nhau một khoảng trắng.
• Trên $D$ dòng tiếp theo, mỗi dòng chứa $R$ kí tự mô tả hình ảnh khung lưới với các món quà treo trên đó. Kí tự * cho biết vị trí một món quà, kí tự . cho biết vị trí một mối nối trên khung lưới.

Ghi ra tập tin văn bản CHONQUA.OUT một số nguyên cho biết số lượng món quà lớn nhất mà An có thể nhận khi đặt vợt trên khung lưới để nhận quà.

• $3 \le K \le D, R \le 1000$;
• 50% test ứng với 50% số điểm của bài có $3 \le D, R \le 100$.