CF1313D Happy New Year

做圣诞老人非常困难。有时候你需要应对一些棘手的情况。 今天圣诞老人来到了节日现场，面前排着 $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$ 个魔法的参数。

输出一个整数，表示圣诞老人最多能让多少个孩子开心。

在第一个样例中，圣诞老人应该施放第一个和第三个魔法。这样除了第 3 个孩子外，其他所有孩子都会开心。 由 ChatGPT 4.1 翻译