codeforces#P1832F. Zombies

Zombies

Description

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.

Input

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

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.

3 3 10 3
0 2
1 7
4 7
3 2 10 3
0 2
1 7
4 7
3 1 10 3
0 2
1 7
4 7
2 1 20 6
11 13
2 14
5 3 7 4
4 6
0 3
4 7
1 5
2 7
6 3 9 4
3 9
4 9
2 5
0 5
6 9
2 3
18
18
16
22
14
26