## https://yukicoder.me/problems/no/866 def solve2(h, w, K, l, cum_dp_array): h1 = h + l - 1 w1 = w + l - 1 answer = 0 for word in range(26): cum_dp = cum_dp_array[word] ans = cum_dp[h1 + 1][w1 + 1] - cum_dp[h1 + 1][w] - cum_dp[h][w1 +1] + cum_dp[h][w] if ans > 0: answer += 1 return answer <= K def solve(H, W, K, cum_dp_array): answer = 0 for h in range(H): for w in range(W): low = 1 high = min( (H - h), (W - w)) while high - low > 1: mid = (high + low) // 2 if solve2(h, w, K, mid, cum_dp_array): low = mid else: high = mid if solve2(h, w, K, high, cum_dp_array): answer += high else: answer += low return answer def main(): H, W, K = map(int, input().split()) C = [] for _ in range(H): C.append(input()) cum_dp_array = [] for word in range(26): dp = [[0] * W for _ in range(H)] for h in range(H): for w in range(W): if ord(C[h][w]) - ord("a") == word: dp[h][w] += 1 cum_dp = [[0] * (W + 1 ) for _ in range(H + 1)] for h in range(H): row = 0 for w in range(W): row += dp[h][w] cum_dp[h + 1][w + 1] = cum_dp[h][w + 1] + row cum_dp_array.append(cum_dp) ans1 = solve(H, W, K, cum_dp_array) if K > 1: ans2 = solve(H, W, K - 1, cum_dp_array) ans1 -= ans2 print(ans1) if __name__ == "__main__": main()