D. Новый год
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Быть дедом Морозом очень сложно. Порой приходится сталкиваться с непростыми ситуациями.

Сегодня дед Мороз пришел на праздник и перед ним выстроились $$$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 5 3
1 3
2 4
3 5
Выходные данные
4
Примечание

В первом примере деду Морозу следует применить первое и третье заклинание. В таком случае счастливыми окажутся все дети кроме третьего.