Vương quốc

Vương quốc X vừa trải qua một đợt thiên tai lớn. Để tái thiết đất nước, nhà vua ban hành một chính sách mới: xây dựng các khu dân cư trên những vùng đất có địa hình bằng phẳng.

Vương quốc có một bản đồ địa hình dạng lưới hình chữ nhật kích thước \(r \times c\). Mỗi ô đất ở hàng \(i\) (\(1 \le i \le r\)), cột \(j\) (\(1 \le j \le c\)) được gọi là ô \((i, j)\) và có độ cao là \(h_{i,j}\).

Một khu dân cư phải được xây dựng 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 \le x \le u \le r\) và \(1 \le y \le v \le c\)). Điều kiện để được cấp phép xây dựng là tất cả các ô đất trong khu vực này phải có cùng độ cao.

Nhà vua muốn biết có bao nhiêu cách chọn một khu đất thỏa mãn yêu cầu trên để xây dựng. 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 vực trong cách chọn này nhưng không thuộc khu vực trong cách chọn kia.

Yêu cầu: Hãy giúp nhà vua đếm số lượng cách chọn khu đất hợp lệ.

Input

• Dòng đầu tiên chứa hai số nguyên \(r\) và \(c\) (\(1 \le r, c \le 2000\)) lần lượt là số hàng và số cột của bản đồ.
• 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 \le h_{i,j} \le 10^9\)) mô tả độ cao các ô đất tại hàng thứ \(i\).

Output

• In ra một số nguyên duy nhất là số cách chọn khu đất hợp lệ.

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

Scoring

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