drept

Fie $X$ o matrice cu $M$ coloane (numerotate de la $1$ la $M$) şi $N$ linii (numerotate de la $1$ la $N$) cu componente din mulţimea $\{ 0, 1 \}$. Pe fiecare linie a matricei se află o singură secvenţă (eventual vidă) formată din elemente egale cu $1$, secvenţă identificată prin poziţia de început (indicele coloanei pe care se află primul $1$ din secvenţă) şi lungimea ei. Restul elementelor de pe linie sunt egale cu $0$.

Cerinţă

Să se determine numărul de dreptunghiuri cu dimensiunile $A$ şi $B$, formate numai din $1$ care se află în matricea $X$. Dreptunghiurile numărate au fie $A$ linii şi $B$ coloane, fie $A$ coloane şi $B$ linii.

Date de intrare

Fişierul de intrare drept.in conţine pe prima linie cele $4$ numere naturale separate prin câte un spaţiu cu semnificaţia din enunţ, în ordinea $M \ N \ A \ B$. Pe fiecare dintre următoarele $N$ linii se află câte două numere naturale separate prin spaţiu, descriind matricea $X$. Mai exact linia $i$ a fişierului se află poziţia de început şi lungimea secvenţei de elemente egale cu $1$ de pe linia $i-1$ a matricei $X$.

Date de ieşire

Fişierul de ieşire drept.out va conţine o singură linie pe care veţi scrie numărul de dreptunghiuri care respectă condiţiile din enunţ.

Restricții și precizări

• $1 \leq N, A, B \leq 2 \ 000 \ 099$
• $1 \leq M \leq 5 \ 000 \ 099$
• $0 \leq$ Lungimea unei secvenţe formată din elemente egale cu $1 \leq M$

Exemplu

drept.in

5 6 2 3
1 5
1 3
1 2
1 1
3 3
2 4

drept.out

3

Explicație

Figură

Cele $3$ dreptunghiuri au colţurile stânga-sus/dreapta-jos:
(1, 1) / (3, 2)
(1, 1) / (2, 3)
(5, 3) / (6, 5)