Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Minimal coverage
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 5002Accepted: 1441Special Judge

Description

Given set of line segments [Li , Ri] with integer coordinates of their end points. Your task is to find the minimal subset of the given set which covers segment [0,M] completely (M is a positive integer).

Input

First line of the input contains number M (1 <= M <= 5000). Subsequent lines of input contain pairs of numbers Li and Ri (abs(Li), abs(Ri) <= 50000). Each pair is placed on separate line. Numbers in the pair are separated with space(s). List of pairs is ended with pair of integers "0 0". i <= 100000

Output

Your program should print in the first line of output the power of minimal subset of segments which covers segment [0, M]. The list of segments of covering subset must follow. Format of the list must be the same as described in input with exception that ending pair "0 0" should not be printed. Segments should be printed in increasing order of their left end point coordinate.

If there is no covering subset then print "No solution" to output.

Sample Input

1
-1 0
-5 -3
2 5
0 0

Sample Output

No solution

Hint

Huge input,scanf is recommended.
Sample input #2
1
-1 0
0 1
0 0

Sample output #2
1
0 1

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator