Saratov Locust
I leaped onto the teacher's head, causing a schoolgirl in the front row to scream. The lecture came to a halt, and I was promptly tossed out of the veranda window onto the ground. It seems they aren't fond of large green grasshoppers here... But I remain hopeful. There's another lecture happening on the neighboring veranda, and perhaps I'll have better luck there.
I've already picked a spot on the neighboring veranda from which it will be most convenient to jump onto someone's head, and now I need to reach it. Naturally, it's best to jump there in a straight line. With each jump, I can cover any whole number of centimeters, up to a maximum of K. Each jump costs me one unit of energy, but fortunately, there's delicious grass growing almost everywhere along my path, which boosts my strength. After each jump, I can refresh myself and gain two whole units of energy. Unfortunately, there are sections along the path where grass doesn't grow. If I land on such a section after a jump, I won't be able to regain my strength.
I am certain that I have enough energy to reach the veranda, but jumping onto a student's or teacher's head is quite exhausting, so I want to have the maximum possible energy reserve when I reach the final point. Help me determine how much my energy reserve at the end will differ from the amount of energy I initially have.
Input
The first line of the input file contains two numbers N and K (0 ≤ N ≤ 1000, 1 ≤ K ≤ 1000) - the number of segments along the path where grass does not grow and the maximum distance of my jump, respectively. The next N lines each contain two numbers a and b (0 ≤ a ≤ b ≤ 10^9) - the starting and ending points of the current segment. It is guaranteed that no two segments overlap and all segments are located between the starting and ending points of my path inclusively. The last line of the input file contains one number X (1 ≤ X ≤ 10^9) - the coordinate of the final point of my path. It can be assumed that I initially start at point 0.
Output
Output a single number - the difference between my final and initial energy reserves.