Ten

Time limit0.5sMemory limit1024 MB

Summary

Count the rectangular submatrices of a positive-integer matrix whose entries sum to exactly 10, with dimensions up to 300 by 300.

Level: Medium6 of 10
Topics: Prefix sum, Two pointers, Binary search, Matrix
Solved: No attempts yet

Problem

The real estate company IC manages a rectangular section of land. The section is divided into $mn$ segments in an $m \times n$ matrix, where the number of rows is $m$ and the number of columns is $n$ . Each segment has a price, which is a positive integer. IC wants to sell a rectangular subsection of the land, and the price of that subsection must be ten. The price of a subsection is the sum of the prices of the segments in it. Several such subsections may exist, so IC wants to know how many candidate subsections it can sell. Write a program that helps IC count the candidate subsections of the land.

For example, the prices of the segments of a land with $5 \times 7$ segments are given as follows.

We can find four candidate subsections to sell, marked by rectangles: the first consists of four segments in the first and second rows spanning from the second to the third columns, the second consists of six segments in the second and third rows spanning from the third to the fifth columns, the third consists of two segments in the first row spanning from the fifth to the sixth columns, and the fourth consists of three segments in the seventh column spanning from the third to the fifth rows. Therefore, for the input above, your program must print 4.

Input

Your program reads from standard input. The first line of the input contains two positive integers $m$ and $n$ ( $1 \le m, n \le 300$ ), the dimensions of the land, separated by a space. Each of the following $m$ lines contains $n$ positive integers $p_{ij}$ , the prices of the segments in the $i$ -th row ( $1 \le i \le m$ , $1 \le j \le n$ , $1 \le p_{ij} \le 10$ ), also separated by a space.

Output

Your program writes to standard output. Print exactly one line containing an integer, the number of rectangular subsections whose price is ten.

Examples2

Example 1
Input
```
3 5
3 1 2 1 4
4 5 2 2 2
4 7 1 1 2
```
Expected output
```
2
```

Example 2

Input

4 6
3 1 2 1 4 6
4 5 2 2 2 7
4 7 1 1 1 9
4 3 3 3 7 2

Expected output