A certain set of segments with integer coordinates of ends \([L_i, R_i]\) is given on a line. Among the given set, choose a subset of segments that completely covers the segment \([0, M]\), (M — natural number) containing the smallest number of segments.
Input
The first line contains the constant M (\(1<=M<=5000\)). Each subsequent line contains a pair of numbers Li and Ri (\(|L_i|,|R_i| < 50000\)), which specifies the coordinates of the left and right ends of the segments. The list ends with a pair of zeros. The total number of segments does not exceed 100,000.
Output
In the first line of the output file print the minimum number of segments required to cover the segment
\([0; M]\). Next, output a list of the covering subset, sorted in ascending order by the coordinates of the left ends of the segments. The list of segments is output in the same format as in the input. The trailing two zeros are not required. If the segment
\([0; M]\) is the original set of segments
\([L_i, R_i]\)< /span> is not possible, a single phrase “No solution” should be output.
Examples
| # |
Input |
Output |
| 1 |
1
-1 0
-5 -3
2 5
0 0
|
No solution |
| 2 |
1
-1 0
0 1
0 0
|
1
0 1
|