#define rep(i, n) for(int i = 0; i < (int)(n); i++) typedef int ll; #include using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); ll h,w,K; std::cin >> h>>w>>K; std::vector s(h); // ll sum[26][2001][2001]; vector>> sum(26,vector>(h+1,vector(w+1))); for (int i = 0; i < h; i++) { std::cin >> s[i]; for (int j = 0; j < w; j++) { int alpha = s[i][j]-'a'; for (int k = 0; k < 26; k++) { sum[k][i+1][j+1] = sum[k][i][j+1] + sum[k][i+1][j] - sum[k][i][j]; } sum[alpha][i+1][j+1]++; } } ll result = 0; vector> size_from(h,vector(w,1)); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { ll l = 1; ll r = min(h-i,w-j); // numより大きいなら小さく // numより小さいなら大きく // K未満の最大値 if(K==1){ l = 0; }else{ while(r-l>1){ ll m = (r+l)/2; ll num = 0; for (int k = 0; k < 26; k++) { ll cou = sum[k][i+m+1][j+m+1]-sum[k][i][j+m+1]-sum[k][i+m+1][j]+sum[k][i][j]; if(cou>0)num++; } if(num1){ ll m = (r+l)/2; ll num = 0; for (int k = 0; k < 26; k++) { ll cou = sum[k][i+m+1][j+m+1]-sum[k][i][j+m+1]-sum[k][i+m+1][j]+sum[k][i][j]; if(cou>0)num++; } if(num <= K){ l = m; }else{ r = m; } } result += l-maxmiman; // Kである最大値。 } } std::cout << result << std::endl; }