ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2136. John vs Santa

Time limit: 1.0 second
Memory limit: 256 MB
John is an ordinary little boy. However, there is one nuance. He is scared to death of Santa Claus. Christmas is coming and John decided to prepare so that he could prevent the appearance of a bearded wizard in his house.
Santa usually enters the house through the chimney, so John decided to block it. In the side view the chimney looks like a checkered rectangle h × w. In each cell there can either be a brick or not. Due to the specific features of the chimney, in each horizontal line the cells, that are not occupied by the bricks, form a non-empty continuous segment.
Santa Claus is represented as a rectangle of a × b cells. In one step, Santa can move left, right, down or up for one square, but at any time he mustn’t cross the cells occupied by the bricks. Santa starts his way above the highest horizontal line and he wants to finish it under the lowest horizontal line.
John is going to add a minimal amount of bricks to the chimney so that Santa won’t be able to get into the house. Note that after he add the bricks, the non-bricked cells in each horizontal line still must form a non-empty continuous segment. In particular, you can not completely block some horizontal with bricks.
Help John to save his Christmas!

Input

The first line contains integers h and w (1 ≤ h ≤ 105; 3 ≤ w ≤ 109) that are the height and width of the chimney, respectively.
The second line contains integers a and b (1 ≤ a ≤ 109; 2 ≤ b ≤ 109) that are the height and width of the rectangle that specifies Santa Claus, respectively.
The following h lines describe the horizontal lines of the chimney. Each line is specified by two integers li and ri (1 ≤ li, ri < w; 2 ≤ li + ri < w) that are the number of bricks from left and right edges, respectively.

Output

In the single line output the minimal required number of the bricks. Note that the answer can be zero.

Sample

inputoutput
7 5
1 2
2 1
1 1
1 1
1 1
2 1
1 1
1 1
1

Notes

Illustration for the first sample, which is ticked, must be placed so that Santa could not get into the house:
Problem illustration
Problem Author: Nikita Sivukhin
Problem Source: "Later is better than never" Contest