#include #include #include #include template std::vector vec(int len, T elem) { return std::vector(len, elem); } using lint = long long; void solve() { int h, w, k; std::cin >> h >> w >> k; auto acc = vec(26, vec(h + 1, vec(w + 1, 0))); for (int i = 1; i <= h; ++i) { for (int j = 1; j <= w; ++j) { char c; std::cin >> c; ++acc[c - 'a'][i][j]; for (auto& vv : acc) { vv[i][j] += vv[i - 1][j] + vv[i][j - 1] - vv[i - 1][j - 1]; } } } auto get = [&](int lx, int ly, int rx, int ry) { static std::vector cnt(26); std::fill(cnt.begin(), cnt.end(), 0); for (int d = 0; d < 26; ++d) { cnt[d] = acc[d][rx][ry] - acc[d][rx][ly - 1] - acc[d][lx - 1][ry] + acc[d][lx - 1][ly - 1]; } return std::count_if(cnt.begin(), cnt.end(), [](auto c) { return c > 0; }); }; lint ans = 0; for (int lx = 1; lx <= h; ++lx) { for (int ly = 1; ly <= w; ++ly) { int dl, dr; { int ok = std::min(h - lx, w - ly) + 1, ng = -1; // [lx, lx + ok] * [ly, ly + ok] >= k while (ok - ng > 1) { int mid = (ok + ng) / 2; if (get(lx, ly, lx + mid, ly + mid) >= k) { ok = mid; } else { ng = mid; } } dl = ok; } { int ok = std::min(h - lx, w - ly) + 1, ng = -1; // [lx, lx + ok] * [ly, ly + ok] > k while (ok - ng > 1) { int mid = (ok + ng) / 2; if (get(lx, ly, lx + mid, ly + mid) > k) { ok = mid; } else { ng = mid; } } dr = ok; } ans += dr - dl; } } std::cout << ans << "\n"; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); solve(); return 0; }