#include #define rep(i,n,m) for(int i = (n); i <(m); i++) #define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--) using namespace std; using ll = long long; int main() { int h, w, k; cin >> h >> w >> k; string table[h]; rep(i, 0, h) cin >> table[i]; int cumsum[26][h+1][w+1]; memset(cumsum, 0, sizeof(cumsum)); rep(c, 0, 26) { char now = c + 'a'; rep(i, 0, h) rep(j, 0, w) { cumsum[c][i+1][j+1] += cumsum[c][i+1][j] + cumsum[c][i][j+1]; cumsum[c][i+1][j+1] -= cumsum[c][i][j]; if (table[i][j] == now) ++cumsum[c][i+1][j+1]; } } // rep(i, 0, h) // rep(j, 0, w) // cout << i << ' ' << j << ' ' << cumsum[1][i+1][j+1] << endl; ll ans = 0; rep(i, 0, h) rep(j, 0, w) { // binary search for lower bound int l = 0; int r = min(h, w); while (l != r) { int mid = (l + r + 1) / 2; if (h < mid+i or w < mid+j) { r = mid - 1; continue; } int cnt = 0; rep(c, 0, 26) cnt += int( cumsum[c][i+mid][j+mid] - cumsum[c][i+mid][j] - cumsum[c][i][j+mid] + cumsum[c][i][j]> 0); if (cnt < k) l = mid; else r = mid - 1; // if (l == r) // cout << i << ' ' << j << ' ' << l << ": " << cnt << endl; } int l_bottom = l; // binary search for upper bound r = min(h, w); l = 0; while (l != r) { int mid = (l + r + 1) / 2; if (h < mid+i or w < mid+j) { r = mid - 1; continue; } int cnt = 0; rep(c, 0, 26) cnt += int( cumsum[c][i+mid][j+mid] - cumsum[c][i+mid][j] - cumsum[c][i][j+mid] + cumsum[c][i][j]> 0); if (k < cnt) r = mid - 1; else l = mid; } ans += (ll) l - l_bottom; // cout << i << ' ' << j << ' ' << l << ' ' << l_bottom << ' ' << l - l_bottom << endl; } cout << ans << endl; return 0; }