2904. Efficient Cartography

单点时限: 5.0 sec

内存限制: 256 MB

During the digitization of the Yandal region map it has become known that it represents a connected area in its bitmap pixel form and is wholly contained within a M × N pixel rectangle. Also, it has the following unique feature: each horizontal or vertical line intersects the region by exactly one segment.
The map was approved for use in portable navigation devices. The screen size of a typical navigator device is A×B pixels. In order to display this particular map the plane should be divided into rectangles of A × B pixels each by horizontal and vertical lines passing by pixel boundaries. Then, each such rectangle (called a tile) containing at least one pixel of map’s area is loaded into the device.
Your task is to choose the positioning of these separating lines for a given map to minimize the total number of tiles to be loaded into the device. You are not allowed to rotate the map or the screen.


The first line contains 4 integers — M (the number of lines), N, A and B.
Each of the next M lines contains two numbers Li and Ri each — the leftmost and the rightmost index of the column containing region’s pixels on the ith horizontal bitmap pixel line.
The limits for possible values are: 1 ≤ M,N ≤ 105, 1 ≤ A,B ≤ 1 000, 1 ≤ Li ≤ Ri ≤ N.


Output the only integer — the minimal possible number of map tiles.


5 7 2 2
1 2
1 3
2 4
3 5
4 5
7 10 3 4
4 7
4 7
1 10
1 10
1 10
4 7
4 7

1 人解决,3 人已尝试。

1 份提交通过,共有 5 份提交。

9.9 EMB 奖励。

创建: 9 年,4 月前.

修改: 3 年前.

最后提交: 8 年,9 月前.

来源: N/A