Dotted Strips

Juku has a paper strip made of $L$ squares, and some of the squares have dots. Juku wants to cut the strip into pieces so that as many pieces as possible have length exactly $M$ squares and exactly $N$ dots each. The strip may only be cut at the boundaries between squares.

The first line contains four integers separated by spaces: $L$ ($1 \le L \le 10^{15}$), $T$ ($0 \le T \le 10^5$), $M$ ($1 \le M \le 10^6$), and $N$ ($0 \le N \le 10^9$). The squares are numbered $1 \ldots L$ starting from one end of the strip.

Each of the next $T$ lines contains two integers: the number of a square with dots, and the number of dots on that square. Each such square has between 1 and 1,000 dots. The squares with dots are given in increasing order of their numbers.

Print one integer: the maximum number of pieces with the required properties that Juku can cut from the strip.