CF1832F.Zombies
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 li until minute ri , non-inclusive — [li,ri) .
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!
输入格式
The first line contains four integers n,k,x and m ( 1≤k≤n≤2000 ; 1≤m≤x≤109 ) — 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 li and ri ( 0≤li<ri≤x ) — the time interval the i -th entrance is defended manually.
输出格式
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.
输入输出样例
输入#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