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