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