Farmer's Field

Time limit1sMemory limit128 MB

Summary

Count placements of a c-by-d or d-by-c rectangle fully inside a field whose every row is one contiguous segment.

Level: Medium7 of 10
Topics: Sliding window, Stack, Prefix sum, Two pointers
Solved: No attempts yet

Problem

Byteland is a rectangle $a$ meters wide and $b$ meters high. Byteasar is a farmer whose field is made of unit squares. In every horizontal layer (row), the squares that belong to the field form a single contiguous segment, although the field as a whole need not be connected from top to bottom.

The king of Byteland has decreed that every farmer must hand over a rectangular area $c$ meters wide and $d$ meters high, made of unit squares, to the crown. The rectangle may be placed in either orientation, so it occupies either $c$ columns by $d$ rows or $d$ columns by $c$ rows, and it must lie entirely inside the farmer's field. The king picks the position. Byteasar hopes there are many legal positions so that the greedy king cannot decide quickly.

Count how many positions the king may choose, that is, the number of placements of the required rectangle (in either orientation) that fit completely inside Byteasar's field. Two placements are the same position only when they cover exactly the same set of squares, so when $c = d$ the two orientations coincide and are counted once.

Write a program that:

reads the description of Byteasar's field and the dimensions of the area demanded by the king,
computes the number of valid positions of that area inside the field,
writes the answer to standard output.

Input

The first line contains four integers $a$ , $b$ , $c$ and $d$ ( $1 \le a, b, c, d \le 5{,}000{,}000$ ): the width and height of Byteasar's field, followed by the width and height of the area demanded by the king.

Each of the next $b$ lines describes one horizontal layer of the field, from top to bottom, with two integers $x$ and $l$ ( $1 \le x \le a$ , $0 \le l \le a$ , $x + l \le a + 1$ ). In that layer the field starts $x - 1$ meters from the left border of Byteland and spans $l$ consecutive unit squares, so it occupies columns $x$ through $x + l - 1$ . A value of $l = 0$ means the layer contains no field squares.

Output

Print a single integer: the number of positions at which the $c$ -by- $d$ rectangle (in either orientation) fits completely inside Byteasar's field.

Hint

The figure shows the field described by the example input; the dark cells belong to the field.

If you use C++, be careful with STL containers given the size of the data; a careless choice can exceed the time or memory limit.

Examples8

Example 1
Input
```
5 6 2 3
1 5
1 3
1 2
1 1
3 3
2 4
```
Expected output
```
3
```
Example 2
Input
```
1 1 1 1
1 1
```
Expected output
```
1
```
Example 3
Input
```
3 3 2 2
1 3
1 3
1 3
```
Expected output
```
4
```
Example 4
Input
```
4 4 1 2
1 4
1 4
1 4
1 4
```
Expected output
```
24
```
Example 5
Input
```
5 3 1 1
1 5
1 0
1 5
```
Expected output
```
10
```
Example 6
Input
```
2 2 3 1
1 2
1 2
```
Expected output
```
0
```
Example 7
Input
```
5 2 1 5
1 5
1 5
```
Expected output
```
2
```
Example 8
Input
```
4 4 2 2
1 4
1 3
2 3
1 4
```
Expected output
```
5
```