OpenKattis

# 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$.

Sample Input 1 Sample Output 1
10 2
500 30
300 8

3400

Sample Input 2 Sample Output 2
10 3
150 5
200 3
100 3

1450