Table with Letters - 2

题意翻译

给一个 $n \times m$ 的字符矩阵和一个限制 $k$，求有多少个**长、宽大于 1** 的子矩阵满足四个角的字母相等且包含不超过 $k$ 个 `a`。 $2 \leq n,m \leq 400, 0 \leq k \leq n \times m$。

题目描述

Vasya has recently started to learn English. Now he needs to remember how to write English letters. He isn't sure about some of them, so he decided to train a little. He found a sheet of squared paper and began writing arbitrary English letters there. In the end Vasya wrote $ n $ lines containing $ m $ characters each. Thus, he got a rectangular $ n×m $ table, each cell of the table contained some English letter. Let's number the table rows from top to bottom with integers from 1 to $ n $ , and columns — from left to right with integers from 1 to $ m $ . After that Vasya looked at the resulting rectangular table and wondered, how many subtables are there, that matches both following conditions: - the subtable contains at most $ k $ cells with "a" letter; - all letters, located in all four corner cells of the subtable, are equal. Formally, a subtable's definition is as follows. It is defined by four integers $ x_{1},y_{1},x_{2},y_{2} $ such that $ 1<=x_{1}&lt;x_{2}<=n $ , $ 1<=y_{1}&lt;y_{2}<=m $ . Then the subtable contains all such cells $ (x,y) $ ( $ x $ is the row number, $ y $ is the column number), for which the following inequality holds $ x_{1}<=x<=x_{2},y_{1}<=y<=y_{2} $ . The corner cells of the table are cells $ (x_{1},y_{1}) $ , $ (x_{1},y_{2}) $ , $ (x_{2},y_{1}) $ , $ (x_{2},y_{2}) $ . Vasya is already too tired after he's been writing letters to a piece of paper. That's why he asks you to count the value he is interested in.

输入输出格式

输入格式

The first line contains three integers $ n,m,k $ $ (2<=n,m<=400; 0<=k<=n·m) $ . Next $ n $ lines contain $ m $ characters each — the given table. Each character of the table is a lowercase English letter.

输出格式

Print a single integer — the number of required subtables.

输入输出样例

输入样例 #1

3 4 4
aabb
baab
baab

输出样例 #1

2

输入样例 #2

4 5 1
ababa
ccaca
ccacb
cbabc

输出样例 #2

1

说明

There are two suitable subtables in the first sample: the first one's upper left corner is cell $ (2,2) $ and lower right corner is cell $ (3,3) $ , the second one's upper left corner is cell $ (2,1) $ and lower right corner is cell $ (3,4) $ .