Hostel

Arash is organizing an onsite final for the IOI, the International Olympiad in Imagination. $N$ participants are coming, and Arash needs to book a hostel for the participants. Arash has already decided on a nearby hostel where he will book the necessary beds.

There are $M$ types of beds. For a given type of bed $i$, it costs $c_ i$ dollars per bed to rent it and there are $b_ i$ beds of that type available for booking.

The International Olympiad in Imagination is not very good at mathematics involving non-imaginary numbers, so they need your help. They want to know the minimum possible cost to book all the required beds at the hostel. Can you help them?

Input

The first line contains two integers, the number of participants $N$ ($1 \leq N \leq 100$) and the number of types of beds $M$ ($1 \leq M \leq 5$).

Then, $M$ lines follow, containing the numbers $c_ i$ ($100 \leq c_ i \leq 1\, 000$) and $b_ i$ ($1 \leq b_ i \leq 100$) as described above.

There will always be enough beds for all the participants.

Output

Output a single integer on a line – the minimum possible cost for the Olympiad to rent all the necessary beds.

Scoring

Your solution will be tested on a number of test cases. If you pass all of them, you will get $100$ points. Otherwise, you will get $0$ points.

Explanation of Sample 1

In the first example, we buy $8$ beds of the cheapest type for a total cost of $2400$. Then, we buy $2$ beds of the more expensive type for a cost of $1000$. The total is $3400$.

10 2
500 30
300 8

3400

10 3
150 5
200 3
100 3

1450