Optimal Milk Procurement

Due to the low profit margin in the dairy industry, reducing the cost of raw materials (milk) is crucial. Marry Dairy procures milk from several farmers, each offering a fixed unit price and a maximum daily supply. Every day, Marry Dairy must purchase an integer amount of milk from each farmer, up to that farmer's maximum production.

Given the daily milk demand and, for each farmer, the unit price and maximum supply, your task is to determine the minimum total cost required to procure at least the demanded amount of milk.

Input Format:
The first line contains two integers \(M\) and \(N\) where \(M\) is the amount of milk required and \(N\) is the number of farmers. Each of the following \(N\) lines contains two integers representing the unit price and the maximum amount of milk available from a farmer.

Output Format:
Output a single integer representing the minimum total cost to procure at least \(M\) units of milk.

Note: It is guaranteed that the total available milk from all farmers is at least \(M\).

inputFormat

The input starts with two integers (M) (required milk amount) and (N) (number of farmers). This is followed by (N) lines, each containing two integers: the unit price and the maximum milk supply for each farmer.

outputFormat

Output a single integer representing the minimum total cost to procure at least (M) units of milk.

sample

10 3
5 5
3 7
4 6

21