Единственное различие между двумя версиями этой задачи — ограничение на \(k\), ограничение по времени и ограничение по памяти. Делать взломы можно только в том случае, если решены обе версии задачи.
Дореми живет в дождливой стране, состоящей из \(n\) городов, пронумерованных от \(1\) до \(n\).
По метеорологической трансляции было предсказано распределение дождей в ближайшие \(m\) дней. В \(i\)-й день дождь пойдет в городах, находящихся на отрезке \([l_i, r_i]\). Город называется сухим, если в ближайшие \(m\) дней в нем не будет дождя.
Оказалось, что Дореми обладает особой способностью. Она может выбрать \(k\) дней, и в течение этих дней дождя не будет. Дореми хочет вычислить максимальное количество сухих городов после использования специальной силы.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество сухих городов.
Примечание
В первом наборе входных данных, если Дореми использует свою силу в дни
- \(1,2\), то город \(2\) будет сухим;
- \(2,3\), то ни один город не будет сухим;
- \(1,3\), то ни один город не будет сухим;
Таким образом, существует не более \(1\) сухого города.
Во втором наборе входных данных, если Дореми предотвращает
- дождь в дни \(1,2\), то города \(1,2\) будут сухими;
- дождь в дни \(2,3\), то города \(4,5\) будут сухими;
- дождь в дни \(1,3\), то города \(1,5\) будут сухими.
Таким образом, существует не более \(2\) сухих городов.
В третьем наборе входных данных оптимальным является предотвращение дождя в дни \(1,2,4,5\).
В четвертом наборе входных данных всегда есть день дождя, который промочит все города, вне зависимости от использования силы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 3 2
1 2
1 2
1 1
5 3 2
1 3
2 4
3 5
10 6 4
1 5
6 10
2 2
3 7
5 8
1 4
100 6 5
1 100
1 100
1 100
1 100
1 100
1 100
1000 2 2
1 1
1 1
20 5 3
9 20
3 3
10 11
11 13
6 18
|
1
2
6
0
1000
17
|