C11WATER - Đọng nước

Giới hạn
  • Thời gian: 0.8s
  • 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

Nền phẳng của một công trường xây dựng đã được chia thành lưới ô vuông đơn vị kích thước m x n ô. Trên mỗi ô (i,j) của lưới, người ta dựng một cột bê tông hình hộp có đáy là ô (i,j) và chiều lao là h ij đơn vị. Sau khi dựng xong, thì trời đổ mưa to và đủ lâu. Giả thiết rằng nước không thấm qua các cột bê tông cũng như không rò rỉ qua các đường ghép giữa chúng.
Yêu cầu: Xác định lượng nước đọng giữa các cột.

Input

  • Dòng đầu tiên chứa 2 số nguyên dương m,n (m, n <=1000)
  • m dòng tiếp theo, dòng thứ i chứa n số nguyên dương, số thứ j là h ij (<=10 6 )

Các số trên cùng một dòng cách nhau ít nhất 1 dấu cách.

Output

  • Khi ra số đơn vị khối nước đọng lại

Example

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

  • Người up: yenthanh132
  • Nguồn bài: Thầy Lê Minh Hoàng