D. Специальная сетка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Задана сетка размера n × m, некоторые узлы которой черные, а остальные белые. Более того, сетка не совсем обычная — в каждом единичном квадрате сетки проведены диагонали.

На рисунке ниже изображен пример такой сетки размера 3 × 5. Четыре узла этой сетки черные, остальные 11 узлов белые.

Требуется посчитать количество таких треугольников на заданной сетке, что:

  • их углы совпадают с белыми узлами, а площадь ненулевая;
  • все стороны проходят по линиям сетки (горизонтальным, вертикальным или диагональным);
  • никакая сторона не содержит черных узлов.
Входные данные

В первой строке записаны два целых числа n и m (2 ≤ n, m ≤ 400). В каждой следующих n строк содержится по m символов (нулей и единиц) — описание сетки. Если j-й символ в i-й строке равен нулю, значит узел на i-й горизонтальной линии и на j-й вертикальной линии покрашен в белый цвет. Иначе этот символ покрашен в черный цвет.

Горизонтальные линии нумеруются от единицы сверху вниз, вертикальные линии нумеруются от единицы слева направо.

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

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

Примеры
Входные данные
3 5
10000
10010
00001
Выходные данные
20
Входные данные
2 2
00
00
Выходные данные
4
Входные данные
2 2
11
11
Выходные данные
0
Примечание

На рисунке ниже красным и синим цветами выделены треугольники, которые считаются в ответе (это не все требуемые треугольники, а только два из них). Зеленым выделен один из неподходящих треугольников. Он не подходит, поскольку не все его стороны проходят по линиям сетки.