Задача №114554. Новый год
Участникам, использующим язык Python3 , рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3 .
Быть дедом Морозом очень сложно. Порой приходится сталкиваться с непростыми ситуациями.
Сегодня дед Мороз пришел на праздник и перед ним выстроились \(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\)-го заклинания.
Выведите одно число, ответ на задачу.
Тесты к этой задаче состоят из семи групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Группа | Баллы | Дополнительные ограничения | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 15 | \(n \leq 10\), \(m \leq 1000\) | 0 | |
| 2 | 11 | \(k = 1\) | – | |
| 3 | 27 | \(k \leq 2\) | 2 | |
| 4 | 30 | \(m \leq 1000\) | 0, 1 | |
| 5 | 17 | – | 0, 1, 2, 3, 4 | Offline-проверка. |
3 5 3 1 3 2 4 3 5
4