Problem C
Annoyed Coworkers

A picture of you, not working. Source: XKCD 303

It’s another day in the office, and you’re a mastermind of not doing any work yourself. Instead, you’ll go to your coworkers for “help,” but secretly have them do all the work.

You’ve determined that the more one of your coworkers helps you, the more annoyed they become. You’ve also been able to determine how much more annoyed a coworker gets everytime you ask them for help. At the beginning of the day, a coworker is initially $a$ annoyed at you. That’s their annoyance level. Everytime you ask them for help though, they become $d$ more annoyed at you – their annoyance level $a$ increases by a constant amount $d$ so that $a=a+d$.

You want to complete a project of $h$ tasks solely with “help” from your coworkers, but you need to be careful not to annoy any of them too much.

What’s the best you can do?

Input

The first line contains $2$ integers $h$ and $c$, where $h$ ($1 \le h \le 100\, 000$) is the number of times you have to ask for help to complete the project, and $c$ ($1 \le c \le 100\, 000$) denotes the number of coworkers you have.

Each of the following $c$ lines contains two positive integers $a$ and $d$, representing a coworker whose initial annoyance level is $a$ and who is getting more annoyed at you by an increase of $d$ every time you ask them for help ($1\le a, d \le 10^9$).

Output

Output a single number, which is the maximum annoyance level any coworker has at you provided you use an optimal strategy to minimize this level. (In other words, of all possible strategies, choose one that minimizes the annoyance level of the worker or workers who are most annoyed at you at the end.)

Sample Input 1 Explanation

You have $4$ coworkers and you need to ask for help $4$ times. Initially, their annoyance levels are $a_1=1, a_2=2, a_3=3, a_4=4$, the increases are $d_1=2, d_2=3, d_3=4, d_4=5$. One optimal solution is to ask for help twice from coworker $1$, once from coworker $2$, and once from coworker $3$, in which case the final annoyance levels are: $a_1=1 + 2 \cdot 2 = 5, a_2=2 + 3 = 5, a_3=3 + 4 = 7, a_4=4$. The coworker that is most annoyed at you is coworker $3$, whose annoyance level at you is $7$. Or, you could ask coworker $1$ for help $3$ times and coworker $2$ once, leaving you with $a_1=1 + 3 \cdot 2 = 7, a_2=2 + 3 = 5, a_3=3, a_4=4$. Both strategies yield the same minimal maximum amount.

4 4
1 2
2 3
3 4
4 5

7

3 2
1 1000
1000 1

1002

5 2
1 1
2 2

5