CF1313D.Happy New Year

Being Santa Claus is very difficult. Sometimes you have to deal with difficult situations.

Today Santa Claus came to the holiday and there were $m$ children lined up in front of him. Let's number them from $1$ to $m$. Grandfather Frost knows $n$ spells. The $i$-th spell gives a candy to every child whose place is in the $[L_i, R_i]$ range. Each spell can be used at most once. It is also known that if all spells are used, each child will receive at most $k$ candies.

It is not good for children to eat a lot of sweets, so each child can eat no more than one candy, while the remaining candies will be equally divided between his (or her) Mom and Dad. So it turns out that if a child would be given an even amount of candies (possibly zero), then he (or she) will be unable to eat any candies and will go sad. However, the rest of the children (who received an odd number of candies) will be happy.

Help Santa Claus to know the maximum number of children he can make happy by casting some of his spells.

当圣诞老人可不容易，有时你得应对各种棘手的情况。

今天，圣诞老人来到一场节日活动，有 $m$ 个孩子排成一队站在他面前。我们把这些孩子从 $1$ 到 $m$ 编号。圣诞老人掌握 $n$ 种魔法咒语。第 $i$ 种咒语会给所有位置在区间 $[L_i, R_i]$ 内的孩子各发一颗糖果。每种咒语最多只能使用一次。此外，已知：若将全部 $n$ 种咒语都使用，则每个孩子至多收到 $k$ 颗糖果。

儿童不宜摄入过多甜食，因此每个孩子最多只能吃一颗糖果；其余多余的糖果将由其母亲和父亲均分。因此，若某个孩子被分配到的糖果总数为偶数（包括零），那么他（她）将无法吃到任何糖果，只能伤心离去；而其余收到奇数颗糖果的孩子则会开心。

请帮助圣诞老人计算：通过选择性地施放部分咒语，最多能让多少个孩子开心？

The first line contains three integers of $n$, $m$, and $k$ ($1 \leq n \leq 100\,000, 1 \leq m \leq 10^9, 1 \leq k \leq 8$) — the number of spells, the number of children and the upper limit on the number of candy a child can get if all spells are used, respectively.

This is followed by $n$ lines, each containing integers $L_i$ and $R_i$ ($1 \leq L_i \leq R_i \leq m$) — the parameters of the $i$ spell.

第一行包含三个整数 $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$ 个法术的参数。

Print a single integer — the maximum number of children that Santa can make happy.

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

In the first example, Santa should apply the first and third spell. In this case all children will be happy except the third.

在第一个例子中，圣诞老人应施放第一个和第三个咒语。此时，除第三个孩子外，所有孩子都将感到开心。