Bob Constructorul

Time limit: 0.5s Memory limit: 256MB Input: Output:

Cerința

Deja îl cunoașteți pe faimosul Bob Constructorul. Acesta a cumpărat teren și vrea să-și construiască o casă. Din păcate, problema este că terenul are o altitudine variabilă.

Terenul are forma unui dreptunghi de lățime de NN metri și de lungime de MM metri. Acesta poate fi împărțit în NMN*M pătrate.
Casa lui Bob va avea forma unui dreptunghi care are laturile paralele cu marginile terenului, iar vârfurile sale coincid cu vârfurile pătratelor.
Laturile casei pot avea lungimi egale si trebuie sa fie de lungimi întregi, mai mari sau egale cu 11.

Tot terenul acoperit de casa lui Bob trebuie să aibă exact aceeași altitudine pentru a preveni prăbușirea casei(Bob Constructorul are cunoștiințele necesare construirii unei case pe teren denivelat, însa nu dorește să muncească atât de mult la casa lui).

Calculați numărul de moduri în care Bob Constructorul îsi poate crea magnifica operă inginerească(casa), respectând cerința.

Notă: Datele de intrare se citesc de la tastatură, iar datele de ieșire se afișează în consolă.

Date de intrare

Prima linie de intrare conține numerele naturale N MN \ M , dimensiunile terenului.
Fiecare dintre următoarele NN linii conține câte MM numere naturale aija_{ij}, înalțimea fiecărei bucați pătratice de teren.

Date de ieșire

Afișați pe prima linie un singur număr, cu semnificația din cerință.

Restricții și precizări

  • 1N,M10001 \le N, M \le 1000
  • 1aij1091 \le a_{ij} \le 10^9
  • Pentru teste in valoare de 20 de puncte, N,M50N, M \le 50.
  • Pentru teste in valoare de 60 de puncte, N,M500N, M \le 500.

Exemplu 1

stdin

5 3
2 2 2
2 2 1
1 1 1
2 1 2
1 2 1

stdout

27 

Exemplu 2

stdin

4 3
1 1 1
1 1 1
2 2 2
2 2 2

stdout

36

Log in or sign up to be able to send submissions!