You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 4.0 seconds
Memory limit: 256.0 MB

# Problem
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!

## Input Format
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.

## Output Format
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.

## Examples
```input
3 3 10 3
0 2
1 7
4 7
```
```output
18
```
-----
```input
3 2 10 3
0 2
1 7
4 7
```
```output
18
```
-----
```input
3 1 10 3
0 2
1 7
4 7
```
```output
16
```
-----
```input
2 1 20 6
11 13
2 14
```
```output
22
```
-----
```input
5 3 7 4
4 6
0 3
4 7
1 5
2 7
```
```output
14
```
-----
```input
6 3 9 4
3 9
4 9
2 5
0 5
6 9
2 3
```
```output
26
```

Now solve the problem and return the code.