Problem Description

Mr. Takahashi is playing a certain game with his friends.

In this game, the objective for the players is to buy buildings, renovate them, and earn as much money as possible.

Mr. Takahashi is currently in second place and must somehow earn more money than Mr. Aoki, who is in first place.

Mr. Takahashi plans to win by obtaining the title of "Renovation King," which is awarded to the player who renovates the most number of times. From his long experience, he knows that he can become the Renovation King by renovating $ K $ more times.

Mr. Takahashi currently owns $ N $ buildings, numbered from $ 1 $ to $ N $. Initially, none of the buildings have been renovated.

For building $i\ (1\ ≦\ i\ ≦\ N)$, the following information is known:

• The initial price of building $ i $ is $ A_i $.
• Renovating building $ i $ once requires an amount equal to the current price of building $ i $.
• The price of building $ i $ increases by $ D_i $ each time it is renovated.

Since Mr. Takahashi is implementing other strategies concurrently, he wants the total cost of the renovations to be as low as possible.

You are asked to find the minimum total cost required to renovate $ K $ times on behalf of Mr. Takahashi.

Input Format

The input is given from the standard input in the following format:

$ K $ $ N $ $ A_1 $ $ D_1 $ $ A_2 $ $ D_2 $ : $ A_N $ $ D_N $

• The first line contains the number of renovations needed to become the Renovation King, $K\ (1\ ≦\ K\ ≦\ 10^8)$.
• The second line contains the number of buildings Mr. Takahashi owns, $N\ (1\ ≦\ N\ ≦\ 10^5)$.
• The next $ N $ lines contain the information about the buildings. The $ i $-th line contains integers $A_i\ (1\ ≦\ A_i\ ≦10^3)$ and $D_i\ (1\ ≦\ D_i\ ≦10^3)$ separated by a space.

Output Format

Output the minimum total cost required to renovate $ K $ times on one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
3
10 3
12 4
15 5

Sample Output #1

50

Sample Input #2

8
4
1 1
10 1
100 1
1000 1

Sample Output #2

36

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $K\ ≦\ 300$ and $N\ ≦\ 300$, you will be awarded $ 30 $ points.
• If you solve the dataset where $K\ ≦\ 5,000$ and $N\ ≦\ 5,000$, you will be awarded an additional $ 10 $ points.
• If you solve the dataset where $K\ ≦\ 10^5$, you will be awarded an additional $ 15 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 45 $ points.

Sample Explanation 1

For example, renovate as follows:
1. Renovate building $ 1 $. The current price of building $ 1 $ is $ 10 $, so the total cost is $ 10 $. After renovation, the price of building $ 1 $ becomes $ 13 $.
2. Renovate building $ 1 $ again. The current price is $ 13 $, so the total cost is $ 23 $. After renovation, the price becomes $ 16 $.
3. Renovate building $ 2 $. The current price is $ 12 $, so the total cost is $ 35 $. After renovation, the price becomes $ 16 $.
4. Renovate building $ 3 $. The current price is $ 15 $, so the total cost is $ 50 $. After renovation, the price becomes $ 20 $.
This way, the total cost for $ 4 $ renovations is $ 50 $.

Sample Explanation 2

Renovate building $ 1 $ $ 8 $ times.

见题面 Input 部分

见题面 Output 部分