#include #include #include #include #include #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() const int INF = 0x3f3f3f3f; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; /*-------------------------------------------------*/ int cnt[26][2000][2000] = {}; int level(int y1, int x1, int y2, int x2) { int res = 0; REP(i, 26) { int tmp = cnt[i][y2][x2]; if (y1 > 0) tmp -= cnt[i][y1 - 1][x2]; if (x1 > 0) tmp -= cnt[i][y2][x1 - 1]; if (y1 > 0 && x1 > 0) tmp += cnt[i][y1 - 1][x1 - 1]; if (tmp > 0) ++res; } return res; } int main() { cin.tie(0); ios::sync_with_stdio(false); // freopen("input.txt", "r", stdin); int h, w, k; cin >> h >> w >> k; vector > c(h, vector(w)); REP(i, h) REP(j, w) cin >> c[i][j]; REP(i, h) { REP(j, w) { REP(k, 26) if (j > 0) cnt[k][i][j] = cnt[k][i][j - 1]; ++cnt[c[i][j] - 'a'][i][j]; } } REP(j, w) { FOR(i, 1, h) REP(k, 26) cnt[k][i][j] += cnt[k][i - 1][j]; } // REP(i, h) { // REP(j, w) cout << cnt[1][i][j] << ' '; // cout << '\n'; // } long long ans = 0; REP(i, h) REP(j, w) { int tmp = (i < j ? h - (j - i) - 1 : h - 1); vector memo(tmp - i + 1, -1); memo[tmp - i] = level(i, j, tmp, j + tmp - i); // cout << tmp << (j == w - 1 ? '\n' : ' '); if (memo[tmp - i] < k) continue; int lb = i - 1, ub = tmp; while (ub - lb > 1) { int mid = (lb + ub) / 2; int l = (memo[mid - i] == -1 ? level(i, j, mid, j + mid - i) : memo[mid - i]); memo[mid - i] = l; (l >= k ? ub : lb) = mid; } int mn = ub; lb = i - 1; ub = tmp; while (ub - lb > 1) { int mid = (lb + ub) / 2; int l = (memo[mid - i] == -1 ? level(i, j, mid, j + mid - i) : memo[mid - i]); memo[mid - i] = l; (l > k ? ub : lb) = mid; } int mx = ub + (memo[tmp - i] <= k ? 1 : 0); ans += mx - mn; // cout << i << ' ' << j << ' ' << mn << ' ' << mx << '\n'; } cout << ans << '\n'; return 0; }