#pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template void chmin(T &t, const T &f) { if (t > f) t = f; } template void chmax(T &t, const T &f) { if (t < f) t = f; } int H, W, K; char C[2010][2010]; int sum[26][2010][2010]; int ansL[2010][2010]; int ansU[2010][2010]; inline int calc(int e, int x0, int x1, int y0, int y1) { return sum[e][x0][y0] - sum[e][x0][y1] - sum[e][x1][y0] + sum[e][x1][y1]; } int main() { for (; ~scanf("%d%d%d", &H, &W, &K); ) { for (int x = 0; x < H; ++x) { scanf("%s", C[x]); } for (int e = 0; e < 26; ++e) { for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) { sum[e][x + 1][y + 1] = sum[e][x + 1][y] + sum[e][x][y + 1] - sum[e][x][y] + ((C[x][y] - 'a' == e) ? 1 : 0); } } Int ans = 0; for (int x = 0; x < H; ++x) for (int y = 0; y < W; ++y) { int lo, hi; lo = 0; hi = min(H - x, W - y) + 1; if (x > 0 && y > 0) { chmax(lo, ansU[x - 1][y - 1] - 2); } for (; lo + 1 < hi; ) { const int mid = (lo + hi) / 2; int cnt = 0; for (int e = 0; e < 26; ++e) { if (calc(e, x, x + mid, y, y + mid) > 0) { ++cnt; } } ((cnt >= K + 1) ? hi : lo) = mid; } ansU[x][y] = hi; lo = 0; if (x > 0 && y > 0) { chmax(lo, ansL[x - 1][y - 1] - 2); } for (; lo + 1 < hi; ) { const int mid = (lo + hi) / 2; int cnt = 0; for (int e = 0; e < 26; ++e) { if (calc(e, x, x + mid, y, y + mid) > 0) { ++cnt; } } ((cnt >= K) ? hi : lo) = mid; } ansL[x][y] = hi; ans += ansU[x][y] - ansL[x][y]; } printf("%lld\n", ans); } return 0; }