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