CF1832F Zombies

波利卡普在一个后末日的环境中玩电脑游戏。僵尸已经占领了世界，波利卡普和一小队幸存者正在抵御试图入侵他们基地的成群僵尸。僵尸从第 $0$ 分钟开始入侵，持续 $x$ 分钟。基地有 $n$ 个入口，每分钟都有一只僵尸试图通过每个入口进入。 幸存者可以抵御僵尸通过入口的方式有两种： - 手动 — 射击通过某个入口的僵尸； - 自动 — 在某个入口设置电围栏来电击僵尸。 如果在某分钟内某个入口被以任一或两种方式防御，则没有僵尸能够通过。 每个入口由一名专门的幸存者防守。第 $i$ 个入口在第 $l_i$ 分钟到第 $r_i$ 分钟（不包括第 $r_i$ 分钟）期间以手动方式防守 — $[l_i, r_i)$。 有 $k$ 个发电机可以用于自动防守入口。每个入口必须连接到一个发电机，但一个发电机可以连接到多个入口（甚至没有连接到任何入口）。每个发电机将工作**连续** $m$ 分钟。波利卡普可以独立选择每个发电机的开启时间，$m$ 分钟的时间间隔必须完全在 $[0, x)$ 时间间隔内。 波利卡普是个奇怪的玩家。他希望游戏对他来说尽可能困难。因此，他希望将每个入口连接到一个发电机，并选择每个发电机的时间，以便尽可能多的僵尸进入基地。请帮助他实现这个目标！

第一行包含四个整数 $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 < r_i \le x$) — 第 $i$ 个入口的手动防守时间区间。

打印一个整数 — 在波利卡普将每个入口连接到某个发电机并选择每个发电机的时间后，能够进入基地的最大僵尸数量。