← 返回题目列表

Codeforces · 1313/D

D. 新年快乐

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

成为圣诞老人非常困难。有时您必须应对困难的情况。

今天圣诞老人来过节了,他面前有$$$m$$$的孩子们。我们将它们从 $$$1$$$ 到 $$$m$$$ 编号。弗罗斯特祖父懂得 $$$n$$$ 咒语。第 $$$i$$$ 咒语会为每个位于 $$$[L_i, R_i]$$$ 范围内的孩子提供一颗糖果。每个法术最多可以使用一次。还知道,如果使用所有咒语,每个孩子最多将收到 $$$k$$$ 糖果。

孩子吃太多糖果不好,所以每个孩子最多只能吃一颗糖果,剩下的糖果将平均分配给他(或她)的爸爸妈妈。所以事实证明,如果给一个孩子均匀数量的糖果(可能为零),那么他(或她)将无法吃任何糖果并且会感到悲伤。然而,其余的孩子(收到奇数糖果)会很高兴。

帮助圣诞老人了解他可以通过施展一些咒语使最多多少个孩子快乐。

输入

第一行包含 $$$n$$$、$$$m$$$ 和 $$$k$$$ 三个整数 ($$$1 \leq n \leq 100\,000, 1 \leq m \leq 10^9, 1 \leq k \leq 8$$$) — 咒语数量、儿童数量和糖果数量上限如果分别使用所有咒语,孩子可以获得。

接下来是 $$$n$$$ 行,每行包含整数 $$$L_i$$$ 和 $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq m$$$) — $$$i$$$ 咒语的参数。

输出

打印一个整数 - 圣诞老人能让快乐的孩子的最大数量。

示例

输入 #1

3 5 3
1 3
2 4
3 5

输出 #1

4

注意

在第一个示例中,圣诞老人应该应用第一个和第三个咒语。在这种情况下,除了第三个孩子之外,所有孩子都会幸福。