CF1832F.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!

波利卡普正在玩一款末日废土题材的电脑游戏。僵尸已经占领了世界，波利卡普与一小队幸存者正共同抵御一波波企图入侵他们基地的僵尸潮。僵尸将从第 $0$ 分钟开始持续入侵 $x$ 分钟。基地共有 $n$ 个入口，且每分钟每个入口都恰好有一只僵尸试图闯入。

幸存者可以对入口进行防御，防御方式有两种：

• 手动防御：向某一入口涌来的僵尸开枪射击；
• 自动防御：在某一入口架设电篱笆以电击僵尸。

若某入口在某分钟内被任一（或两种）方式成功防御，则该分钟内不会有僵尸通过。

每个入口均由一名专属幸存者负责手动防御。第 $i$ 个入口的手动防御时间区间为第 $l_i$ 分钟至第 $r_i$ 分钟（不含右端点），即半开区间 $[l_i, r_i)$。

此外，基地还有 $k$ 台发电机可用于实现自动防御。每台发电机可连接至任意数量（包括零台）的入口，但每个入口必须且只能连接至一台发电机。每台发电机一旦启动，将连续工作恰好 $m$ 分钟。波利卡普可独立决定每台发电机的启动时刻，但其工作的 $m$ 分钟区间必须完全落在总时间区间 $[0, x)$ 内。

波利卡普是一位特立独行的玩家，他希望游戏对他而言尽可能困难。因此，他希望在为每个入口分配发电机、并为每台发电机选定启动时刻时，使得最终成功进入基地的僵尸总数最大化。请帮助他实现这一目标！

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 \lt r_i \le x$) — the time interval the $i$-th entrance is defended manually.

第一行包含四个整数 $n, k, x$ 和 $m$（$1 \le k \le n \le 2000$；$1 \le m \le x \le 10^9$）—— 分别表示入口数量、发电机数量、僵尸入侵持续时间以及所有发电机的总持续时间。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i \lt r_i \le x$）—— 表示第 $i$ 个入口由人工防守的时间区间。

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.

输出一个整数——即在波利卡普将每个入口连接至某个发电机并为每个发电机选择启动时间后，能够进入基地的僵尸的最大数量。