Description

Matrix67 must submit $n$ papers to his teacher next month. The content of each paper can be chosen from $m$ topics. Since the number of topics is limited, Matrix67 has to reuse some topics. The time required to complete papers on different topics varies. Specifically, for topic $i$, if Matrix67 plans to write a total of $x$ papers, then the total time needed for that topic is $A_i \times x^{B_i}$ time units. Given $A_i$ and $B_i$ for each topic, please help Matrix67 determine how to choose the topics for the $n$ papers so that the total time is minimized.

Input Format

The first line contains two integers $n$ and $m$, representing the number of papers to complete and the number of available topics, respectively.
The next $m$ lines each contain two integers. On the $i$-th line, the two numbers represent the time coefficient $A_i$ and the exponent $B_i$ corresponding to topic $i$.

Output Format

Output the minimum total time required to complete $n$ papers.

10 3
2 1
1 2
2 1

19

Hint

Sample Explanation:
Choose topic 1 for $4$ papers, topic 3 for $5$ papers, and topic 2 for the remaining $1$ paper. The total time is $2\times4^1+1\times1^2+2\times5^1=8+1+10=19$. It can be proven that there is no better plan with total time less than $19$.

Constraints:
For $30\%$ of the testdata, $n \le 10$, $m \le 5$.
For $100\%$ of the testdata, $1 \le n \le 200$, $1 \le m \le 20$, $1 \le A_i \le 100$, $1 \le B_i \le 5$.

Translated by ChatGPT 5