Bài 4. Bảng kí tự
An lấy một tờ giấy hình vuông và bắt đầu viết các kí tự tiếng anh tùy ý lên đó. Cuối cùng An đã viết được n dòng, mỗi dòng chứa m kí tự. Cuối cùng, anh ấy nhận được một bảng hình chữ nhật n x m, mỗi ô của bảng chứa một kí tự tiếng anh bất kì. Các dòng của bảng tính từ trên xuống dưới tương ứng các số nguyên từ 1 đến n, và các cột tính từ trái sang phải tương ứng các số nguyên từ 1 đến m.
Sau đó, An nhìn vào kết quả bảng hình chữ nhật và tự hỏi, có bao nhiêu bảng con ở đó thỏa mãn hai điều kiện sau:
Bảng con chứa nhiều nhất là k ô có kí tự ‘a’
Tất cả các kí tự ở bốn góc của hình chữ nhật con là bằng nhau.
Bạn hãy giúp An đếm giá trị mà An quan tâm.
Yêu cầu: cho bảng hình chữ nhật như trên. Đếm số bảng con thỏa mãn hai điều kiện.
Dữ liệu: vào cho trong tệp BAI4.INP:
Dòng đầu tiên chứa 3 số nguyên n, m, k (2 ≤ n, m ≤ 400; 0 ≤ k ≤ n·m).
n dòng kế tiếp, mỗi dòng chứa m kí tự của bảng đã cho. Mỗi kí tự trong bảng là một bảng gồm các chữ cái tiếng anh thường.
Kết quả: đưa ra tệp BAI4.OUT một số nguyên duy nhất — số lượng bảng con cần tìm.
Ví dụ:
BAI4.INP
3 4 4
aabb
baab
baab
BAI4.OUT
2
Ràng buộc:
Subtask 1: 30% test ứng 30% số điểm có n,m≤20.
Subtask 2: 30% test ứng 30% số điểm có n,m≤100.
Subtask 3: 40% test ứng 40% số điểm có n,m≤400.