Hay Purchase Optimization

Farmer John needs to purchase at least H pounds of hay for his cows. He has access to N hay suppliers, each selling packages of hay. Supplier i provides packages weighing P_i pounds at a cost of C_i dollars. Each supplier has an unlimited number of packages available and packages must be purchased whole.

Your task is to compute the minimum cost required to purchase at least H pounds of hay.

Mathematically, you need to determine the minimum total cost such that:

\(\sum_{i=1}^{N} k_i \cdot P_i \ge H\)

where \(k_i\) (non-negative integers) denote the number of packages bought from supplier i and the total cost is \(\sum_{i=1}^{N} k_i \cdot C_i\).

inputFormat

The first line contains two integers H and N, representing the minimum required pounds of hay and the number of suppliers, respectively.

Each of the next N lines contains two integers, P_i and C_i, indicating the weight (in pounds) and cost (in dollars) of a hay package offered by supplier i.

outputFormat

Output a single integer, which is the minimum cost required to purchase at least H pounds of hay.

sample

1 1
1 1

1