题目描述
You are given a matrix A that consists of N rows and M columns. Every number in the matrix is either zero or one. Calculate the number of such triples (i, j, h) where for all the pairs (x, y), where both x and y belong to [1; h] if y ≥ x, A[i+x-1][j+y-1] equals to one. Of course, the square (i, j, i+h-1, j+h-1) should be inside of this matrix. In other words, we're asking you to calculate the amount of square submatrices of a given matrix which have ones on and above their main diagonal.
------ Input ------
The first line of the input consists of two integers - N and M.
The following N lines describe the matrix. Each line consists of M characters that are either zero or one.
------ Output ------
Output should consist of a single integer - the answer to the problem.
------ Example ------
Input:
2 3
011
111
Output:
6
------ Scoring ------
Subtask 1 (9 points): 1 ≤ N,M ≤ 2000, All the numbers in the matrix are equal to one.
Subtask 2 (12 points): 1 ≤ N,M ≤ 10.
Subtask 3 (34 points): 1 ≤ N,M ≤ 30.
Subtask 4 (17 points): 1 ≤ N,M ≤ 150.
Subtask 5 (28 points): 1 ≤ N,M ≤ 2000.
输入格式
见题面
输出格式
见题面