#include #include using namespace std; using ll = long long; int h,w,k; int counts[2001][2001][26]; inline int count_level(int i, int j, int r) { int level = 0; for(int c=0;c<26;++c) { if(counts[i+r-1][j+r-1][c] - counts[i+r-1][j-1][c] - counts[i-1][j+r-1][c] + counts[i-1][j-1][c] > 0) { ++level; if(level > k) break; } } return level; } inline int binary_search(int i, int j, int k) { int ok = 1, ng = min(h-i, w-j)+2, r; // ok: 半径 ok のとき level <= k; // ng: 半径 ng のとき level > k; while(ng-ok > 1) { r = (ok+ng) / 2; if(count_level(i, j, r) > k) { ng = r; } else { ok = r; } } return ok; } int main() { cin >> h >> w >> k; char c; for(int i=1;i<=h;++i) { for(int j=1;j<=w;++j) { for(int k=0;k<26;++k) { counts[i][j][k] = counts[i-1][j][k] + counts[i][j-1][k] - counts[i-1][j-1][k]; } cin >> c; ++counts[i][j][c-'a']; } } ll ans = 0; for(int i=1;i<=h;++i) { for(int j=1;j<=w;++j) { ans += binary_search(i, j, k) - binary_search(i, j, k-1); } } cout << ans << endl; }