Số cách chọn nền chữ nhật

[rogp10]

[COCI 2014/15 - vòng 2, bài 4 - 120/650 điểm]

Đề bài Phú hộ Bân có một vuông đất cò bay thẳng cánh được chia thành M x N ô hình chữ nhật. Lão muốn tìm một vị trí đẹp trên đó để xây một căn khác to hơn căn 1 x 1 hiện tại. Lão rất ghét phải đi lên rồi xuống dốc trong nhà nên nền nhà phải bằng phẳng và cũng là hình chữ nhật. Hãy đếm số cách để chọn nền đất xây nhà.

# M = 3, N = 2
1 2 2 1
1 1 1 2
3 1 1 2
(có 6 khả năng - ô 2x2 là 3 rồi)

I/O

• Input: stdin
  • Dòng đầu tiên: Hai số nguyên M là số dòng, N là số cột, M, N <= 1000
  • M dòng tiếp theo, mỗi dòng gồm N số nguyên dương <= 10^9 là độ cao của ô đó
• Output: stdout
  • Một số nguyên duy nhất là số cách chọn nền.

Giới hạn

• 24 điểm: N, M <= 50
• 72 điểm: N, M <= 500 ▊