Минимальное покрытие
Среди заданного множества отрезков прямой с целочисленными координатами концов [L_i, R_i] необходимо выбрать подмножество наименьшей мощности, целиком покрывающее отрезок [0, M], где M – целое положительное число.
Входные данные
В первой строке записано целое число M (1 ≤ M ≤ 5000). В последующих строках перечислены пары целых чисел L_i и R_i (|L_i|, |R_i| ≤ 50000), каждая пара с новой строки, числа в парах отделены друг от друга одним или несколькими пробелами. Список завершается парой нулей. Список содержит не более 100000 пар чисел, включая пару нулей.
Выходные данные
Программа должна формировать в первой строке требуемое минимальное число отрезков из исходного множества, необходимое для покрытия отрезка [0, M]. Далее должен следовать список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe, завершающую пару нулей выводить не следует.
Если покрытие отрезка [0, M] исходным множеством отрезков [L_i, R_i] невозможно, то следует вывести единственную фразу "No solution".