Hostel

Interview

Time limit1sMemory limit1024 MB

Summary

Given M bed types with a price and a stock limit each, find the cheapest way to book beds for N participants.

Level: Easy3 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Arash is organizing the onsite final of PO, the Swedish Potato Peeling Olympiad. $N$ participants will come, and Arash needs to book sleeping places for them. Arash has chosen a nearby hostel.

The hostel has $M$ types of beds. A bed of type $i$ costs $c_i$ kronor, and there are $b_i$ beds of that type available. The hostel has no current bookings, so you can book as many beds as needed.

The Potato Peeling Olympiad team is not strong in math and needs your help. Find the minimum possible cost of booking the beds they need.

Input

The first line contains two integers, the number of participants $N$ ( $1 \leq N \leq 100$ ) and the number of bed types $M$ ( $1 \leq M \leq 5$ ). The next $M$ lines each contain $c_i$ ( $100 \leq c_i \leq 1000$ ) and $b_i$ ( $1 \leq b_i \leq 100$ ) as described above.

There are always enough beds for all participants.

Output

Print one integer on a line: the minimum possible cost for the Swedish Potato Peeling Olympiad to rent beds at the hostel for one night.

Constraints

$1 \leq N \leq 100$ , $1 \leq M \leq 5$ , $100 \leq c_i \leq 1000$ , $1 \leq b_i \leq 100$

Hint

In the first sample, you buy all 8 of the cheapest beds for a total of 2400, then you buy two of the slightly more expensive beds for a total of 1000. The final price is 3400.

Examples2

Example 1
Input
```
10 2
500 30
300 8
```
Expected output
```
3400
```
Example 2
Input
```
10 3
150 5
200 3
100 3
```
Expected output
```
1450
```