Vào thời trung cổ, vùng đất LQDOJ đã bị một đợt sóng thần quét qua làm hư hại rất nhiều nhà cửa, ruộng vườn. Trong đó có tòa lâu đài của lãnh chúa vùng đất. Do đó lãnh chúa đã ra lệnh khẩn cấp chọn vị trí để xây lâu đài mới của mình.

Vùng đất giờ đây có dạng một bảng hình chữ nhật kích thước \(r \times c\) gồm các ô đất hình vuông. Ô đất ở hàng \(i\) \((1 \leq i \leq r)\), cột \(j\) \((1 \leq j \leq c)\) được gọi là ô \((i, j)\) và đất nơi đây có độ cao \(h_{i,j}\) so với mực nước biển. Tòa lâu đài sẽ được xây trên một khu đất hình chữ nhật \((x, y, u, v)\) (với \((x , y)\) là tọa độ góc trái trên và \((u, v)\) là tọa độ góc phải dưới trong đó \(1 \leq x \leq u \leq r\) và \(1 \leq y \leq v \leq c\)) sao cho các ô đất thuộc khu đất này có cùng độ cao.

Lãnh chúa muốn biết có bao nhiêu cách chọn khu đất thỏa mãn yêu trên cầu để xây lâu đài. Hai cách chọn được xem là khác nhau khi và chỉ khi tồn tại một ô đất thuộc khu đất trong cách chọn này nhưng không thuộc khu đất trong cách chọn kia.

Yêu cầu: Bạn hãy giúp lãnh chúa đếm xem ngài có bao nhiêu cách chọn khu đất thỏa mãn yêu cầu nêu trên.

Input

• Dòng đầu tiên chứa hai số nguyên \(r\) và \(c\) \((1 \leq r, c \leq 2000)\) lần lượt số hàng và số cột của bảng hình chữ nhật mô tả vùng đất.
• Trong \(r\) dòng tiếp theo, dòng thứ \(i\) chứa \(c\) số nguyên \(h_{i, 1}, h_{i, 2}, \ldots, h_{i, c}\) \((1 \leq h_{i,j} \leq 10^{9})\) mô tả độ cao các ô vuông đất tại hàng thứ \(i\).

Output

• In ra số cách chọn khu đất để xây lâu đài cho lãnh chúa.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(r, c \leq 50\).
• Subtask \(2\) (\(40\%\) số điểm): \(r, c \leq 500\).
• Subtask \(3\) (\(20\%\) số điểm): \(h_{i, j} \leq 10\).
• Subtask \(4\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3
1 1 1
2 2 2
3 3 3

18

5 6
1 1 1 1 5 5
1 1 1 5 5 4
3 2 2 2 2 4
3 3 2 2 2 4
3 3 2 2 2 4

91