Cheap Travels

Memory limit: 32 MB

A coach trip by a transcontinental motorway lasts many days so payments for hotels are a serious part of the travel cost. For the sake of safety and comfort coaches travel only in the daytime and can make at most km a day. During the trip the driver and passengers spend nights in hotels (it does not concern the beginning and the end of the trip).

So far travels were planned to minimize the number of nights spent in hotels. To decrease the cost the firm organizing travels decided to find out if it is commercially viable to plan the travels in such a way that the sum of payments for hotels is minimal (even if it extends the time of travel). Offers of hotels situated along the motorway should be used in calculations. Each offer consists of the distance between the hotel and the beginning of the route and the price of a single night for one person in the hotel.

The travel is one-way. The route does not fork. At each point of the route the coach is only once. To identify a hotel it is enough to give its distance from the beginning of the route, i.e. at each point of the route there is at most one hotel. Nights at the beginning and at the end of the route are not planned. The number of passengers is constant and in every hotel all of them and the driver pay for the night the same amount — according to the offer. We assume that the capacities of hotels are big enough to place all the passengers.

There is at least one hotel in every fragment of the route of length km, so travel can be always made according to the given conditions.

Task

Write a program that:

• reads from the standard input the following data: the length of the route, the number of hotels and the offers of hotels;
• finds two plans of travel:
  • a plan of the cheapest travel (the sum of payments for hotels is minimal); if there is more than one solution the program should chose the one with the minimal number of nights in hotels,
  • a plan of the shortest travel (the number of nights in hotels is minimal); if there is more than one solutions the program should chose the one with the minimal sum of payments for hotels;
• writes the results, i.e. two plans of travel — the cheapest and the shortest, to the standard output.

Input

In the first line of the standard input there are written two positive integers separated by a single space. The first integer is the length of the route given in kilometres. The second integer is the number of hotels, , .

In the following lines there are written the offers of hotels — one offer in one line. The offers are ordered according to the increasing distance of hotels from the beginning of the route. Each offer consists of two positive integers separated by a single space. The first integer is the distance of the hotel from the beginning of the route and is given in kilometres. The second integer is the price of a single night in this hotel and is not greater than .

Output

In the first line of the standard output there should be written the plan of the cheapest travel, i.e. the distances from the beginning of the route of the hotels in which we decide to spend nights. In the second line there should be written, in a similar way, the plan of the shortest travel. The numbers in each line should be separated by a single space.

Example

For the input data:

2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40

the correct result is:

400 1200 
400 1200 

Task author: Stanislaw Waligorski.