A15876 | Zombies

Polycarp plays a computer game in a post-apocalyptic setting. The zombies have taken over the world, and Polycarp with a small team of survivors is defending against hordes trying to invade their base. The zombies are invading for $x$ minutes starting from minute $0$ . There are $n$ entrances to the base, and every minute one zombie attempts to enter through every entrance.

The survivors can defend the entrances against the zombies. There are two options:

- manually — shoot the zombies coming through a certain entrance;
- automatically — set up an electric fence on a certain entrance to fry the zombies.

If an entrance is defended either or both ways during some minute, no zombie goes through.

Every entrance is defended by a single dedicated survivor. The $i$ -th entrance is defended manually from minute $l_i$ until minute $r_i$ , non-inclusive — $[l_i, r_i)$ .

There are $k$ generators that can be used to defend the entrances automatically. Every entrance should be connected to exactly one generator, but a generator can be connected to multiple entrances (or even none of them). Each generator will work for exactly $m$ consecutive minutes. Polycarp can choose when to power on each generator independently of each other, the $m$ minute long interval should be fully inside the $[0, x)$ time interval.

Polycarp is a weird gamer. He wants the game to be as difficult as possible for him. So he wants to connect each entrance to a generator and choose the time for each generator in such a way that as many zombies as possible enter the base. Please, help him to achieve that!

The first line contains four integers $n, k, x$ and $m$ ( $1 \le k \le n \le 2000$ ; $1 \le m \le x \le 10^9$ ) — the number of entrances, the number of generators, the duration of the zombie invasion and the duration of all generators.

The $i$ -th of the next $n$ lines contains two integers $l_i$ and $r_i$ ( $0 \le l_i < r_i \le x$ ) — the time interval the $i$ -th entrance is defended manually.

Print a single integer — the largest number of zombies that can enter the base after Polycarp connects each entrance to some generator and chooses the time for each generator.