310433: CF1832F. Zombies

Memory Limit：256 MB Time Limit：4 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

F. Zombiestime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 $l_i$ until minute $r_i$, non-inclusive — $[l_i, r_i)$.

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!

Input

The first line contains four integers $n, k, x$ and $m$ ($1 \le k \le n \le 2000$; $1 \le m \le x \le 10^9$) — 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 $l_i$ and $r_i$ ($0 \le l_i < r_i \le x$) — the time interval the $i$-th entrance is defended manually.

Output

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.

ExamplesInput
3 3 10 3
0 2
1 7
4 7
Output
18
Input
3 2 10 3
0 2
1 7
4 7
Output
18
Input
3 1 10 3
0 2
1 7
4 7
Output
16
Input
2 1 20 6
11 13
2 14
Output
22
Input
5 3 7 4
4 6
0 3
4 7
1 5
2 7
Output
14
Input
6 3 9 4
3 9
4 9
2 5
0 5
6 9
2 3
Output
26

Input

题意翻译

### 题目描述 给定 $n$ 个左闭右开区间 $I_i = [l_i, r_i)$（$1\leq i\leq n$）。 找出 $k$ 个左闭右开区间 $J_j = [a_j, b_j)$（$1\leq j\leq k$）满足 $a_j + m = b_j$ 且 $0\leq a_j < b_j \leq x$，以及一个长度为 $n$ 的数组 $p_i\in [1, k]$，最大化 $\sum_{i = 1} ^ n |[0, x) \backslash (I_i\cup J_{p_i})|$。 你只需求出最大化的值，不需要给出构造方案。 区间 $[l, r)$ 的长度为 $r - l$，即 $|[l, r)| = r - l$。 $1\leq k\leq n\leq 2000$，$1\leq m\leq x \leq 10 ^ 9$，$0\leq l_i < r_i \leq x$。 ### 输入格式 第一行四个整数 $n, k, x, m$。 接下来 $n$ 行，每行两个整数 $l_i, r_i$。 ### 输出格式 输出一行一个整数表示答案。 翻译贡献者：[Alex_Wei](https://www.luogu.com.cn/user/123294)。

Output

题目大意：
Polycarp 在一个末日主题的游戏中，扮演一名幸存者抵御僵尸入侵。游戏持续 x 分钟，有 n 个入口，每分钟每个入口有一个僵尸尝试进入。幸存者可以用两种方式防御入口：手动射击或设置电网自动防御。每个入口有一个手动防御的时间段 [l_i, r_i)。有 k 个发电机可以用来设置电网，每个发电机可以连续工作 m 分钟。Polycarp 需要连接每个入口到一个发电机，并选择合适的时间启动发电机，以便尽可能多的僵尸进入基地。

输入数据格式：
第一行包含四个整数 n, k, x 和 m（1 ≤ k ≤ n ≤ 2000, 1 ≤ m ≤ x ≤ 10^9）——入口数量、发电机数量、僵尸入侵持续时间、发电机工作时间。
接下来 n 行，每行包含两个整数 l_i 和 r_i（0 ≤ l_i < r_i ≤ x）——第 i 个入口的手动防御时间段。

输出数据格式：
打印一个整数——在 Polycarp 连接每个入口到某个发电机并选择发电机启动时间后，能够进入基地的僵尸的最大数量。

例：
输入
3 3 10 3
0 2
1 7
4 7
输出
18

输入
3 2 10 3
0 2
1 7
4 7
输出
18

输入
3 1 10 3
0 2
1 7
4 7
输出
16

输入
2 1 20 6
11 13
2 14
输出
22

输入
5 3 7 4
4 6
0 3
4 7
1 5
2 7
输出
14

输入
6 3 9 4
3 9
4 9
2 5
0 5
6 9
2 3
输出
26题目大意： Polycarp 在一个末日主题的游戏中，扮演一名幸存者抵御僵尸入侵。游戏持续 x 分钟，有 n 个入口，每分钟每个入口有一个僵尸尝试进入。幸存者可以用两种方式防御入口：手动射击或设置电网自动防御。每个入口有一个手动防御的时间段 [l_i, r_i)。有 k 个发电机可以用来设置电网，每个发电机可以连续工作 m 分钟。Polycarp 需要连接每个入口到一个发电机，并选择合适的时间启动发电机，以便尽可能多的僵尸进入基地。 输入数据格式： 第一行包含四个整数 n, k, x 和 m（1 ≤ k ≤ n ≤ 2000, 1 ≤ m ≤ x ≤ 10^9）——入口数量、发电机数量、僵尸入侵持续时间、发电机工作时间。 接下来 n 行，每行包含两个整数 l_i 和 r_i（0 ≤ l_i < r_i ≤ x）——第 i 个入口的手动防御时间段。 输出数据格式： 打印一个整数——在 Polycarp 连接每个入口到某个发电机并选择发电机启动时间后，能够进入基地的僵尸的最大数量。 例： 输入 3 3 10 3 0 2 1 7 4 7 输出 18 输入 3 2 10 3 0 2 1 7 4 7 输出 18 输入 3 1 10 3 0 2 1 7 4 7 输出 16 输入 2 1 20 6 11 13 2 14 输出 22 输入 5 3 7 4 4 6 0 3 4 7 1 5 2 7 输出 14 输入 6 3 9 4 3 9 4 9 2 5 0 5 6 9 2 3 输出 26

Source/Category

加入题单

上一题 下一题 算法标签：