僵尸

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

僵尸从第 (0) 分钟开始，持续进攻 (x) 分钟。基地有 (n) 个入口，每分钟都有一只僵尸尝试通过每个入口。

入口可以由人工或电网防守。若某个入口在某一分钟被至少一种方式防守，则这一分钟没有僵尸从该入口通过。

第 (i) 个入口在半开区间 ([l_i,r_i)) 内由人工防守。

另有 (k) 台发电机。每个入口必须连接到恰好一台发电机，一台发电机可以连接任意多个入口。每台发电机恰好连续工作 (m) 分钟，其工作区间必须完整位于 ([0,x)) 内；各台发电机的启动时刻可以独立选择。

请选择每个入口连接的发电机以及每台发电机的启动时刻，使进入基地的僵尸数量最大。

输入格式

第一行四个整数 (n,k,x,m)。

接下来 (n) 行，第 (i) 行两个整数 (l_i,r_i)。

输出格式

输出能够进入基地的最大僵尸数量。

样例输入 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

数据范围

对于全部数据，(1\le k\le n\le2000)，(1\le m\le x\le10^9)，(0\le l_i<r_i\le x)。

题目来源：Codeforces 1832F。