Сколько на небе звезд? Юному программисту Поликарпу этот вопрос не дает покоя! Он сфотографировал звездное небо на цифровой фотоаппарат и теперь изучает получившуюся монохромную цифровую фотографию. Фотография представляет собой прямоугольную матрицу, состоящую из n строк по m символов в каждой строке. Символ равен '1', если соответствующий пиксель фотографии белый, и '0', если черный.
Поликарп считает, что нашел звезду на фотографии, если обнаружил белый пиксель, окруженный четырьмя соседними по стороне пикселями, которые все тоже белые:
1
111
1
звезда на фотографии Поликарп хочет вырезать прямоугольный участок из фотографии и подарить маме. На этом участке должно быть изображено не менее k звезд. Изображения звезд могут пересекаться, иметь общие белые пиксели. Прямоугольный участок он будет вырезать так, что его границы окажутся параллельны сторонам фотографии, а разрезы будут проходить точно по границам между пикселями.
Теперь Поликарпа мучает вопрос — сколько существует способов вырезать участок из фотографии, который удовлетворяет требованиям выше? Помогите Поликарпу найти это количество.
Выходные данные
Выведите искомое количество участков на заданной фотографии.
Примечание
Будем ниже использовать нумерацию столбцов и строк от 1, координатами (p, q) обозначать клетку в строке p, столбце q.
В первом примере Поликарп должен вырезать любой участок, который содержит прямоугольник с противоположными углами в клетках (1, 1) и (3, 4). Такому условию удовлетворяют только прямоугольники с противоположными углами в (1, 1) и в (x, y), где x ≥ 3 и y ≥ 4.
Во втором примере подойдет любой прямоугольник, каждая сторона которого имеет длину не менее четырех. Возможные размеры прямоугольников — 4 × 4, 4 × 5, 5 × 4 и 5 × 5. Такие фигуры можно вырезать 4 способами, 2 способами, 2 способами и 1 способом соответственно.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6 2
111000
111100
011011
000111
|
6
|
|
2
|
5 5 4
11111
11111
11111
11111
11111
|
9
|