Cheap Travels

Interview

Time limit1sMemory limit128 MB

Summary

Pick a sequence of hotels so consecutive stops are at most 800 km apart, minimizing total price (ties: fewest nights), and also minimizing nights (ties: lowest price).

Level: Medium6 of 10
Topics: Dynamic programming, Array, Two pointers, Greedy
Solved: No attempts yet

Problem

A long coach trip along a transcontinental motorway spans many days, so hotel payments make up a large share of the travel cost. For safety and comfort the coach travels only in the daytime and can cover at most 800 km in a single day. Every night of the trip (but not its start or its end) is spent in a hotel along the route.

Until now, trips were planned to minimize the number of nights spent in hotels. To cut costs, the travel company now also wants to know whether it is worthwhile to plan a trip so that the total of the hotel payments is as small as possible, even if that makes the trip longer.

The route runs one way and does not fork. The coach passes each point of the route exactly once. A hotel is identified by its distance from the start of the route, and there is at most one hotel at any point. No night is spent at the start or the end of the route. The number of passengers is fixed, and in every hotel each passenger and the driver pay the same price for one night, as stated in that hotel's offer. Every hotel can accommodate all of them.

Every stretch of the route that is 800 km long contains at least one hotel, so a trip can always be arranged under these rules. (If the whole route is at most 800 km long, the coach can drive straight through and spend no nights at all.)

Your program must find two travel plans:

the cheapest travel: the total of the hotel payments is the smallest possible; if several plans reach that smallest total, choose the one that uses the fewest nights;
the shortest travel: the number of nights spent in hotels is the smallest possible; if several plans reach that smallest number, choose the one with the smallest total payment.

Input

The first line contains two positive integers separated by a single space: the route length $d$ in kilometres and the number of hotels $h$ , where $d \le 16000$ and $h \le 1000$ .

Each of the next $h$ lines describes one hotel offer and contains two positive integers separated by a single space: the hotel's distance from the start of the route in kilometres, and the price of one night per person at that hotel (at most 1000). The offers are listed in order of increasing distance from the start.

Output

Print two lines.

On the first line print the cheapest travel: its total hotel payment and the number of nights it uses, separated by a single space.

On the second line print the shortest travel: its total hotel payment and the number of nights it uses, separated by a single space.

(When the whole route is at most 800 km long, a plan may use no nights; then both its total payment and its number of nights are 0.)

Examples4

Example 1

Input

Expected output

35 2
35 2

Example 2
Input
```
500 1
250 7
```
Expected output
```
0 0
0 0
```
Example 3
Input
```
1600 3
400 1
800 100
1200 1
```
Expected output
```
2 2
100 1
```

Example 4

Input

Expected output

3 3
100 2