Grasshopper#5267
On a bright morning, a large green grasshopper is exploring a spacious veranda. It spots a particularly lush and delicious patch of grass growing at the far end and decides to reach it in the most efficient way possible.
The grasshopper starts at position and wants to reach position . It can jump any whole number of centimeters up to a maximum of with each jump. Each jump costs the grasshopper one unit of energy. Luckily, tasty grass grows along most of the path; after each jump, if the grasshopper lands on such a patch, it is able to refresh itself and regains two units of energy. However, there are certain segments along the path where no grass grows. If the grasshopper lands in one of these segments after a jump, it does not regain any energy.
The grasshopper knows it has enough energy to reach its destination. Still, it wants to arrive at the delicious patch with as much energy as possible. Help the grasshopper determine the difference between its final and initial energy reserves upon reaching the end of the path.
The first line contains two integers and (0 \le N \le 1000, 1 \le K \le 1000), the number of segments along the path without grass and the maximum distance of a jump, respectively. Each of the next lines contains two integers and (0 \le a \le b \le 10^9) — the starting and ending points of each such segment. No two segments overlap, and all segments are between the starting and ending points of the path, inclusive. The final line contains one integer (1 \le X \le 10^9), representing the coordinate of the endpoint of the path. You may assume the grasshopper starts at point .
Output a single integer — the difference between the grasshopper's final and initial energy reserves.
Example 1