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.

样例

Input
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
Output
5
5

1 人解决,3 人已尝试。

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

9.9 EMB 奖励。

创建: 8 年,8 月前.

修改: 2 年,5 月前.

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

来源: N/A

题目标签