CF253D.Table with Letters - 2

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 < _x_2 ≤ n, 1 ≤ _y_1 < _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.

瓦西娅最近开始学习英语，现在他需要记住如何书写英文字母。他对其中一些字母的写法还不确定，因此决定稍作练习。

他找到一张方格纸，并在上面随意书写英文字母。最终，瓦西娅共写了 $ n $ 行，每行包含 $ m $ 个字符。于是，他得到了一个 $ n \times m $ 的矩形表格，其中每个单元格都包含某个英文字母。我们将表格的行从上到下编号为 $ 1 $ 到 $ n $，列从左到右编号为 $ 1 $ 到 $ m $。

之后，瓦西娅观察了这个矩形表格，并思考：满足以下两个条件的子表格（subtable）有多少个？

• 该子表格中至多含有 $ k $ 个字母为 "a" 的单元格；
• 该子表格四个角上的单元格中所含的字母全部相等。

形式化地，一个子表格由四个整数 $ x_1,\ y_1,\ x_2,\ y_2 $ 定义，满足 $ 1 \le x_1 < x_2 \le n $，$ 1 \le y_1 < y_2 \le m $。该子表格包含所有满足 $ x_1 \le x \le x_2 $ 且 $ y_1 \le y \le y_2 $ 的单元格 $ (x,\ y) $（其中 $ x $ 为行号，$ y $ 为列号）。该子表格的四个角单元格为 $ (x_1,\ y_1) $、$ (x_1,\ y_2) $、$ (x_2,\ y_1) $、$ (x_2,\ y_2) $。

瓦西娅在纸上写完字母后已经非常疲惫，因此请你帮他计算出他所关心的这个数值。

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.

第一行包含三个整数 $n$、$m$、$k$（$2 \le n, m \le 400$；$0 \le k \le n\cdot m$）。

接下来的 $n$ 行，每行包含 $m$ 个字符——即给定的表格。表格中的每个字符均为一个小写英文字母。

Print a single integer — the number of required subtables.

输出一个整数——所需子表格的数量。

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).

第一个样例中有两个合适的子表格：第一个子表格的左上角单元格为 $(2, 2)$，右下角单元格为 $(3, 3)$；第二个子表格的左上角单元格为 $(2, 1)$，右下角单元格为 $(3, 4)$。