Volodya wants to beautifully congratulate his wife on their wedding anniversary and is going to give her a bouquet of n flowers.
Arriving at a flower shop, Volodya discovered that a bouquet can be made from flowers of m different types, and the number of flowers of each type is not limited. Volodya knows that the first flower of the i-th species in the bouquet makes his wife happier by a
i, and each next flower
this way she becomes happier on b
i. That is, if in the bouquet x
i > 0 flowers of type i, then flowers of this type make Volodya's wife happier by a
i + (x
i − 1) · b
i.
Like any loving husband, Volodya wants to please his wife as much as possible. Therefore he wants to know by what maximum amount her happiness can increase from a bouquet, picked from the flowers available in the store.
Input data format
The first line contains two integers n and m (1 ≤ n ≤ 10
9 , 1 ≤ m ≤ 100 000) — required
the number of flowers in the bouquet and the number of flowers available.
Each of the following m lines describes the i-th kind of flowers and contains two integers a
i and b
i (0 ≤ a
i , b
i ≤ 10
9 ) — an increase in happiness from the first flower of the i-th species and an increase in happiness from each subsequent flower of this species.
Output data format
In a single line print a single number — the maximum increase in happiness that Volodya's wife can get from a bouquet of n flowers.
Examples
| # |
Input |
Output |
| 1 |
4 3
50
14
2 2 |
14 |
| 2 |
5 3
5 2
4 2
3 1
| 16 |