BOB - Bob xây nhà

Giới hạn
  • Thời gian: 0.5s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Bob mua một khu đất có dạng hình chữ nhật có chiều rộng là N mét và chiều cao là M mét, và mảnh đất được chia thành MxN ô vuông nhỏ, mỗi ô vuông có một độ cao khác nhau.

Bob muốn xây một ngôi nhà trên mảnh đất này. Anh muốn chọn một khu đất hình chữ nhật, có các cạnh song song với cạnh của mảnh đất, tuy nhiên, độ cao của tất cả ô đất trong vùng được chọn phải bằng nhau.

Hãy đếm số cách Bob có thể chọn khu vực để xây nhà.

Input

  • Dòng đầu tiên là 2 số N và M (N, M ≤ 1000)
  • N dòng sau, mỗi dòng gồm M số, số thứ j của hàng i là giá trị a[i][j] thể hiện chiều cao của ô đất có tọa độ (i, j) (a[i][j] ≤ 10 9 )

Output

Số nguyên duy nhất là kết quả của bài toán

Example

Input:
5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1
Output: 
27

  • Người up: yellowflash12
  • Nguồn bài: COCI