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 metri și de lungime de metri. Acesta poate fi împărțit în 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 .
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 , dimensiunile terenului.
Fiecare dintre următoarele linii conține câte numere naturale , î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
- Pentru teste in valoare de 20 de puncte, .
- Pentru teste in valoare de 60 de puncte, .
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