P16818 [HackerEarth] You are given a NxM matrix consisting of 0s and 1s. Find the number of square frames with no 1s (each cell is 0) in this matrix. A frame of a fixed square is a group of cells each of th
提高
题目描述

You are given a NxM matrix consisting of 0s and 1s. Find the number of square frames with no 1s (each cell is 0) in this matrix. A frame of a fixed square is a group of cells each of them is one of the leftmost, rightmost, topmost or bottommost cells. Thus a square frame with the side length 1 contains 1 cell, with the side length 2 contains 4, with the side length 3 - 8 cells, with the side length 4 - 12 cells.

Input
The first line contains two integers N and M. Next N lines contain M characters each. Every character is either 1 or 0.

Output
Output one integer - the number of square frames consisting only of 0s.

Constraints
1 ≤N, M ≤ 2000
1 ≤N, M ≤ 10 in 40% of the test data
1 ≤N, M ≤ 100 in 70% of the test data

SAMPLE INPUT
3 4
0100
0100
0000

SAMPLE OUTPUT
12

输入格式

见题面

输出格式

见题面

样例输入
97 92 00000000000000000010000000000000000000000000000000100000000010000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000010000000000000000000000000000000000000000000100000000000000000000000000 00000000000000000000000000000001000000001000100001001000000000000001010000000000000000000000 00000100000000000000010000000100001000000000000010000000000000000000001000000010000000000000 00000000000000000000000000000000000000000001000000000000000000001000000000000000000000000000 00000000000000000000000000000000000000000000100000000000100000000000010000000000000000000000 00000000000000000000000001000000000000000000000000000010000000100100000000000000000000000000 00000000000000000000000000000000000000000000100001000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000 00000000000000000000000010000000000001000000000000000000000000000000000000000000000000000000 00000000000000000000000001000000000000000000000000000000100000000010000000000000000000001000 00000000000000000100000000000000000000000000000000000100000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000 00000000000000000000000000000000000000000000000000000000001100000000100000000011100000001000 00000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000 00000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000010000000000000000000000000000000000000000000000000100000000100 00000000000000000000010000000000000000000000000000000000000000000000000000000000100000000000 00100000000000000000000000000000000000000000000000010000000000000000000000000000000000001000 00000000000000000000000000000000000000000000000000000000000000000000000100000000000000000011 00000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000 10000101000000000000000000000000000000000000000010000000001000000000001000000000000000000000 10000001000010000000000000000010000000000000000000000000000000000000000000000000000000010000 00000000000000000000001000000000000000000000000000100000000000000000000000000000000000000000 00000000000000000000000000000000000000000001000000000000000000000000000010000100000000000000 00100000000000000100000000000000000000000100000000010000000000000000000000000000100000000000 00000000000000000000000000000010000000000000001000100010000010000000000000000000000010000001 00000000000000000000000000001000000000000000000000000000000000000000000000000000010000000000 01000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000001100000000000000000000000000000000000000000000000000000000000000 00000000001000000000000000000000000100000000000000000000000000100001000000000001000100100000 01000000000010000000000000010000000000000000001000000010000000000000000000000000000000000000 00000000000000000000000000000010000000000000000000000000000000000000000000000000000001010000 00000000000000000100000000000000000000000001000000000000000000000000000000000000000000000000 00000001000000000000000000000000000000000000000000001000000000000000000000000000000000000000 00000000100000000000000000000000000000000000100010000000000100000000000000001000000000000000 00000000000000000000001000000000000000000000000000000000000000010000000100000000001000000000 00000000000000000000000000000000100000000000000010000000000000100000000000000000000000000000 00100000000000000000000000000000000000000000100000000000000000000000000000000000000000000000 00000010000000000000000000100000010000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000001000000000000000001000000000000000000000001000 00000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000010000000000100 00000000000000000000000000000000000000010000000000001000000000000000000000000000000000000000 00000100000000000000010000000000000000000000000000000000001000000000000000000000000000000000 00000000000000000000000001000000000000100000000000000000000000001000000000000000000000010000 00000000000000000000000000000000000000000000000000000000000000000000000010000000000000000001 00000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000 00100000000000000010000000000000000000000000000000000000000000000000000000000000000000000100 00000000000100000000000000000001000000000000000000000100001000000000000000000000000000000100 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000010000000000000000000000000000000010000000000000000000000000000000000000000 00000000000000000100000000000000000000000000000000000010000000000000000000000000000000000000 00001000000000000000000000000010000010000000000000000000000000000000000000000000000010000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000010000000000000001000000000000000000000000000000000100000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 01000000000000000000000000000000000010000100000000000000000000000000000000000000010000000000 00000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000100000000001000100000000010000000000000000000000000000000010000000000 00000000000000100000000000000000000010000000000000100100000000000000000000000000000000000000 00000000000000010000000000000000000000000000000000000000000001000000000000000000000000000000 00000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000 00000001000000000000000000000000000000000000000000000000000000000000000000000000000000010000 01100010000000000000000000000000000000000000000010000000000000000000000000000000000000000000 00000000010000000000000100000000000000000000000000000100000000000000000000000000000000000000 00000000000000000000000000001010000000000001000000000001000000000000000000000000000000000100 00000101000000000000000000000000100000000000000000000000000000100000000000000000000000000000 00000000000000100000000001000000000000100000000010000000000010000000000000000101000000000000 00000000000000000000000000000000010000000000000000000000000000000100000000000000000000000000 00000001000000000000000000000000000000000000001000000000000000000000000000000000000000000000 00000010000000000000000000000000000000000001000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000100000000000000000000000000000100000000010000000000000000000000000000000000000000 00000000000000000000010000000000000000000000000000000000000000000000000000000010000000000000 00000000000000000000000000000000000000000101000000000000010000000000000000010000000000000001 00000000000000010000000000000000000000000000000000100000000000000000000000000000001000000000 10000000000100000000000001000000000000000100000000000000000100000000000000010000000000000000 00000000000000000100000000100000000000000000000000000000000011000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000 00000000000000000000000000000000000000000010000000000000000000000000000000000000001000000000 00000001000000001000000010000000000000000000000000000010000000000000000000000000000000000000 00000000000000000000000000000000000000000000001000000000000000000000000000000000000000001000 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000001100010000000000000000000000000000000000010001000000 00000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000 00000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000001000000001000000001001000000100000000000100000000000000000000000 00000000000000000000000000000000000000000000000000100000000000000000000000000000001000000000 00000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000 00000000000000000000000000010000010000000000000000000000000000000000000000000000000000100000 00000000100000000000001000000000000000100000000000000000000000000000000000000000000000000000
样例输出
66950