坡旅甲在世界末日后的环境中玩电脑游戏。僵尸已经占领了世界,波利卡普和一小队幸存者正在抵御试图入侵他们基地的僵尸群。僵尸从 $$$0$$$ 分钟开始入侵 $$$x$$$ 分钟。基地有 $$$n$$$ 个入口,每分钟都有一个僵尸试图通过每个入口进入。
幸存者可以保卫入口免受僵尸袭击。有两种选择:
- 手动——射击从某个入口进来的僵尸;
- 自动——在某个入口设置电围栏来炸僵尸。
如果某个入口在某一分钟内受到单向或双向防守,则没有僵尸可以通过。
每个入口都由一名专注的幸存者保卫。从 $$$l_i$$$ 分钟到 $$$r_i$$$ 分钟,第 $$$i$$$ 个入口由手动防守,不包括 $$$[l_i, r_i)$$$。
有 $$$k$$$ 生成器可用于自动保卫入口。每个入口都应该连接到一台发电机,但一台发电机可以连接到多个入口(甚至没有一个入口)。每个发电机将连续工作 $$$m$$$ 分钟。 Polycarp 可以选择何时独立地为每个发电机供电,$$$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$$$ 个入口被手动防守的时间间隔。
输出
打印一个整数——Polycarp 将每个入口连接到某个生成器并选择每个生成器的时间后,可以进入基地的僵尸的最大数量。
示例
输入 #1
3 3 10 3 0 2 1 7 4 7
输出 #1
18
输入 #2
3 2 10 3 0 2 1 7 4 7
输出 #2
18
输入 #3
3 1 10 3 0 2 1 7 4 7
输出 #3
16
输入#4
2 1 20 6 11 13 2 14
输出#4
22
输入 #5
5 3 7 4 4 6 0 3 4 7 1 5 2 7
输出 #5
14
输入 #6
6 3 9 4 3 9 4 9 2 5 0 5 6 9 2 3
输出 #6
26