Задача: Минимальное покрытие
На прямой задано некоторое множество отрезков с целочисленными координатами концов \([L_i, R_i]\). Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок \([0, M]\), (M — натуральное число), содержащее наименьшее число отрезков.
Входные данные
В первой строке указана константа M (\(1<=M<=5000\)). В каждой последующей строке записана пара чисел Li и Ri (\(|L_i|,|R_i| < 50000\)), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.
Выходные данные
В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка
\([0; M]\). Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка
\([0; M]\) исходным множеством отрезков
\([L_i, R_i]\) невозможно, то следует вывести единственную фразу “
No solution”.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1
-1 0
-5 -3
2 5
0 0
|
No solution |
| 2 |
1
-1 0
0 1
0 0
|
1
0 1 |
Ваш ответ: