Optimal Paper Assignment

Matrix67 must submit n papers next month. There are m topics available, but since the topics are limited, some topics must be chosen more than once. For each topic i, if Matrix67 writes x_i papers on that topic, the total time required is given by the formula

$$A_i \times x_i^{B_i}$$

where A_i and B_i are provided for each topic. Your task is to determine how many papers to assign to each topic (assigning 0 or more papers to each topic with a total of n papers) in order to minimize the overall time spent.

inputFormat

The first line contains two integers n and m representing the total number of papers and the number of topics respectively. Each of the following m lines contains two integers A_i and B_i for the i-th topic.

outputFormat

Output a single integer which is the minimum total time required to complete all n papers.

sample

3 2
1 2
2 1

5