#pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include using namespace std; using ll = long long; using VI = vector; using VL = vector; #define FOR(i,a,n) for(int i=(a);i<(n);++i) #define each(i, a) for(auto &i : a) templateinline vector vec(size_t a) { return vector(a); } templateinline auto vec(size_t a, Ts... ts) { return vector(ts...))>(a, vec(ts...)); } template class acc2d { int h, w; vector>& dat; public: acc2d(vector>& _dat) : dat(_dat), h(_dat.size()), w(_dat[0].size()) { FOR(i, 0, h)FOR(j, 1, w)dat[i][j] += dat[i][j - 1]; FOR(i, 1, h)FOR(j, 0, w)dat[i][j] += dat[i - 1][j]; } T sum(int y1, int x1, int y2, int x2) { T ret = dat[y2][x2]; if (0 < y1)ret -= dat[y1 - 1][x2]; if (0 < x1)ret -= dat[y2][x1 - 1]; if (0 < y1 && 0 < x1)ret += dat[y1 - 1][x1 - 1]; return ret; } T sum(int y2, int x2) { return sum(0, 0, y2, x2); } }; int main() { int h, w, k; scanf("%d %d %d", &h, &w, &k); auto dat = vec(26, h, w); FOR(y, 0, h) { char s[20]; scanf("%s", s); FOR(x, 0, w)++dat[s[x] - 'a'][y][x]; } vector> acc; each(i, dat)acc.emplace_back(i); ll ans = 0; FOR(y, 0, h)FOR(x, 0, w) { int l, r; { int ok = 0, ng = min(h - y, w - x) + 1; while (ng - ok > 1) { int mid = ok + ng >> 1; int kind = 0; FOR(i, 0, 26) { if (acc[i].sum(y, x, y + mid - 1, x + mid - 1))++kind; } if (kind <= k)ok = mid; else ng = mid; } r = ok; } { int ok = 0, ng = min(h - y, w - x) + 1; while (ng - ok > 1) { int mid = ok + ng >> 1; int kind = 0; FOR(i, 0, 26) { if (acc[i].sum(y, x, y + mid - 1, x + mid - 1))++kind; } if (kind < k)ok = mid; else ng = mid; } l = ok; } ans += r - l; } printf("%lld\n", ans); return 0; }