有 $m$ 个孩子，编号为 $1 \sim m$。

圣诞老人会 $n$ 种魔法，第 $i$ 种魔法可以给所有编号在区间 $[L_i, R_i]$ 内的孩子各发一个糖果。每种魔法最多使用一次，并且已知如果所有魔法都使用，每个孩子至多收到 $k$ 个糖果。

你可以控制这 $n$ 种魔法的使用情况，请你求出最多有多少个孩子收到奇数个糖果。

数据范围：$1 \leq n \leq 10^5$，$1 \leq m \leq 10^9$，$1 \leq k \leq 8$。

时空限制：$2$s / $500$MiB。