// includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // }}} using namespace std; using ll = long long; // accum2D range2D range2Dloop {{{ #include using loop2d_int = long long; template < class T > void accum2D(T &val, int h, int w) { for(int i = 1; i < h; i++) for(int j = 0; j < w; j++) val[i][j] += val[i - 1][j]; for(int i = 0; i < h; i++) for(int j = 1; j < w; j++) val[i][j] += val[i][j - 1]; } template < class T > auto range2D(T &val, int y1, int x1, int y2, int x2, int h, int w) { using V = typename std::remove_reference::type; if(y2 >= h) y2 = h - 1; if(x2 >= w) x2 = w - 1; if(y1 > y2 || x1 > x2) return static_cast< V >(0); V res(val[y2][x2]); if(y1 - 1 >= 0) res -= val[y1 - 1][x2]; if(x1 - 1 >= 0) res -= val[y2][x1 - 1]; if(y1 - 1 >= 0 && x1 - 1 >= 0) res += val[y1 - 1][x1 - 1]; return res; } template < class T, class V = typename std::remove_reference< decltype(T()[0][0]) >::type > auto range2Dloop(T &val, loop2d_int ty1, loop2d_int tx1, loop2d_int y2, loop2d_int x2, int h, int w) { if(ty1 > y2 || tx1 > x2) return static_cast< V >(0); loop2d_int y1 = ty1 % h; if(y1 < 0) y1 += h; loop2d_int x1 = tx1 % w; if(x1 < 0) x1 += w; y2 += y1 - ty1; x2 += x1 - tx1; loop2d_int gy = y2 / h; loop2d_int gx = x2 / w; y2 %= h; x2 %= w; V res(0); if(gy == 0 && gx == 0) { res += range2D< T >(val, y1, x1, y2, x2, h, w); } else if(gy == 0) { res += range2D< T >(val, y1, x1, y2, w - 1, h, w); res += range2D< T >(val, y1, 0, y2, x2, h, w); res += range2D< T >(val, y1, 0, y2, w - 1, h, w) * (gx - 1); } else if(gx == 0) { res += range2D< T >(val, y1, x1, h - 1, x2, h, w); res += range2D< T >(val, 0, x1, y2, x2, h, w); res += range2D< T >(val, 0, x1, h - 1, x2, h, w) * (gy - 1); } else { res += range2D< T >(val, y1, x1, h - 1, w - 1, h, w); // UL res += range2D< T >(val, 0, x1, y2, w - 1, h, w); // DL res += range2D< T >(val, y1, 0, h - 1, x2, h, w); // UR res += range2D< T >(val, 0, 0, y2, x2, h, w); // DR res += range2D< T >(val, y1, 0, h - 1, w - 1, h, w) * (gx - 1); // U res += range2D< T >(val, 0, 0, y2, w - 1, h, w) * (gx - 1); // D res += range2D< T >(val, 0, x1, h - 1, w - 1, h, w) * (gy - 1); // L res += range2D< T >(val, 0, x1, h - 1, x2, h, w) * (gy - 1); // R res += range2D< T >(val, 0, 0, h - 1, w - 1, h, w) * (gy - 1) * (gx - 1); // C } return res; } // }}} int h, w, k; string f[2000]; int g[26][2000][2000]; int cnt(int y1, int x1, int y2, int x2) { int res = 0; for(int c = 0; c < 26; c++) res += !!range2D(g[c], y1, x1, y2, x2, h, w); return res; } // レベルp以上 の物の数を求める ll solve(int p) { if(k == 27) return 0; // 1 - w <= u = y - x <= h - 1 ll res = 0; for(int u = 1 - w; u <= h - 1; u++) { // x = y - u int c = 0; int v = -1; for(int y = max(0, 0 + u); y <= min(h - 1, w - 1 + u); y++, v--) { int x = y - u; while(v + 1 <= 0 and cnt(y + v + 1, x + v + 1, y, x) >= p) v++, c++; res += c; } } return res; } int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> h >> w >> k; for(int i = 0; i < h; i++) { cin >> f[i]; for(int j = 0; j < w; j++) g[f[i][j]-'a'][i][j]++; } for(int c = 0; c < 26; c++) accum2D(g[c], h, w); cout << solve(k) - solve(k + 1) << endl; return 0; }