FMI NO STRESS 12 | Hemodinamică

Se dau două matrice binare $A$ și $B$, fiecare cu $N$ linii și $M$ coloane. Definim distanța Hamming dintre două submatrice determinate de colțurile stânga-sus $(x_1, y_1)$ și dreapta-jos $(x_2, y_2)$ ca fiind numărul de poziții $(i, j)$ cu proprietatea că $x_1 \leq i \leq x_2$, $y_1 \leq j \leq y_2$ și $A_{i,j} \neq B_{i, j}$.
Vom nota cu $H(x_1, y_1, x_2, y_2)$ distanța Hamming dintre cele $2$ submatrice determinate de colțurile stânga-sus $(x_1, y_1)$ și dreapta-jos $(x_2, y_2)$ în matricele $A$ și $B$.

Cerință

Să se calculeze

Date de intrare

Pe prima linie se vor găsi numerele $N$ și $M$. Pe următoarele $N$ linii se află câte $M$ cifre binare, reprezentând elementele matricei $A$. Pe următoarele $N$ linii se află câte $M$ cifre binare, reprezentând elementele matricei $B$.

Date de ieșire

Se va afișa un singur număr, $\sum_{1 \leq x_1 \leq x_2 \leq N} \sum_{1 \leq y_1 \leq y_2 \leq M} H(x_1, y_1, x_2, y_2)$.

Restricții și precizări

• $1 \leq N, M \leq 1 \ 000$;
• $A_{i,j}, B_{i, j} \in \{0, 1\}, \forall i \in \{1, 2, \dots, N\}, \forall j \in \{1, 2, \dots, M\}$;
• Pentru $30$ de puncte, $1 \leq N, M \leq 50$;
• Pentru restul de $70$ de puncte, nu există restricții suplimentare.

Exemplu

stdin

3 3
1 0 1
1 1 0
0 0 1
0 0 1
1 0 1
0 1 1

stdout

49

Explicație

De exemplu, pentru submatricea determinată de punctele $(1, 2)$ și $(3, 3)$, distanța Hamming este $3$, deoarece $A_{2,2} \neq B_{2,2}$, $A_{2,3} \neq B_{2,3}$ și $A_{3,2} \neq B_{3,2}$. Suma distanțelor Hamming pentru toate submatricele determinate de două perechi de puncte este $49$.