Bob's House Site

Time limit1sMemory limit64 MB

Summary

Count the subrectangles of an N by M elevation grid whose covered cells all have equal height.

Level: Medium6 of 10
Topics: Stack, Matrix, Dynamic programming
Solved: No attempts yet

Problem

Bob is a well known builder. He bought a piece of land and wants to build a house on it, but the land does not have the same elevation everywhere.

The land is a rectangle divided into $N \times M$ square cells, $N$ rows by $M$ columns. Bob's house is also a rectangle. Its sides are parallel to the sides of the land and its corners meet corners of cells. Every cell the house covers must have the same elevation, otherwise the house collapses.

Count the number of ways Bob can place his house. A house that covers a single cell counts as one way.

Input

The first line contains two integers $N$ and $M$ ( $1 \le N, M \le 1000$ ).

Each of the next $N$ lines contains $M$ integers. The $j$ -th number $a_{ij}$ is the elevation of the cell in row $i$ , column $j$ ( $1 \le a_{ij} \le 10^9$ ).

The input is large, so use a fast reading method. In C++ use scanf instead of cin, in Java use BufferedReader instead of Scanner.

Output

Print the number of ways on one line.

Hint

In the first example, the rectangle with opposite corners (0,0) and (1,1) and the rectangle with opposite corners (0,0) and (0,2) both sit at elevation 2, and the rectangle with opposite corners (2,0) and (2,2) and the rectangle with opposite corners (1,2) and (2,2) both sit at elevation 1. The first number in the parentheses is the row and the second is the column, counted from 0.

Examples9

Example 1
Input
```
5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1
```
Expected output
```
27
```
Example 2
Input
```
4 3
1 1 1
1 1 1
2 2 2
2 2 2
```
Expected output
```
36
```
Example 3
Input
```
1 1
1000000000
```
Expected output
```
1
```
Example 4
Input
```
1 5
1 2 3 4 5
```
Expected output
```
5
```
Example 5
Input
```
1 6
7 7 7 7 7 7
```
Expected output
```
21
```
Example 6
Input
```
6 1
4
4
4
4
4
4
```
Expected output
```
21
```
Example 7
Input
```
4 4
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1
```
Expected output
```
16
```

Example 8

Input

2 3
1 1000000000 1000000000
1 1000000000 1

Expected output

Example 9
Input
```
3 4
5 5 3 3
5 5 3 1
2 2 2 1
```
Expected output
```
23
```