D. Таблица с буквами - 2
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

Вася недавно начал изучать английский язык. Сейчас ему нужно выучить, как пишутся буквы латинского алфавита. Поскольку он еще не до конца запомнил некоторые из них, он решил немного потренироваться.

Он нашел клетчатый лист бумаги и начал писать на нем произвольные буквы латинского алфавита. В конце концов Вася написал n строк по m символов в каждой. Таким образом, он получил прямоугольную таблицу размера n × m, в каждой клетке которой была написана некоторая буква латинского алфавита. Пронумеруем строки этой таблицы сверху вниз целыми числами от 1 до n, а столбцы слева направо целыми числами от 1 до m.

После этого, взглянув на полученную прямоугольную таблицу, Вася заинтересовался следующим вопросом: сколько существует подтаблиц, для которых выполняются следующие два условия:

  • в подтаблице содержится не более k клеток с символом «a»;
  • символы, находящиеся во всех четырех угловых клетках подтаблицы, совпадают.

Формально, подтаблица определяется следующим образом. Она задается четырьмя целыми числами x1, y1, x2, y2 такими, что 1 ≤ x1 < x2 ≤ n, 1 ≤ y1 < y2 ≤ m. Тогда в подтаблице содержатся все такие клетки (x, y) (x — номер строки, y — номер столбца), для которых выполняются неравенства x1 ≤ x ≤ x2, y1 ≤ y ≤ y2. Угловыми клетками таблицы считаются клетки (x1, y1), (x1, y2), (x2, y1), (x2, y2).

Вася уже слишком устал, выписывая буквы на лист бумаги. Поэтому он просит Вас посчитать интересующую его величину.

Входные данные

В первой строке заданы три целых числа n, m, k (2 ≤ n, m ≤ 400; 0 ≤ k ≤ n·m).

Далее в n строках записано по m символов — заданная таблица. Каждый символ таблицы является строчной буквой латинского алфавита.

Выходные данные

Выведите единственное число — требуемое количество подтаблиц.

Примеры
Входные данные
3 4 4
aabb
baab
baab
Выходные данные
2
Входные данные
4 5 1
ababa
ccaca
ccacb
cbabc
Выходные данные
1
Примечание

В первом примере имеется две искомые подтаблицы: первая имеет верхний левый угол в клетке (2, 2) и правый нижний угол в клетке (3, 3), вторая имеет верхний левый угол в клетке (2, 1) и правый нижний угол в клетке (3, 4).