← 返回题目列表

Codeforces · 1832/F

F. 僵尸

中文机器翻译题面 查看原题

坡旅甲在世界末日后的环境中玩电脑游戏。僵尸已经占领了世界,波利卡普和一小队幸存者正在抵御试图入侵他们基地的僵尸群。僵尸从 $$$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