Lễ giáng sinh năm nay, Nam quyết định tặng bạn gái mình \(n\) bông hoa.

Tại cửa hàng hoa, có \(m\) loại hoa khác nhau. Với loại hoa thứ \(i\), nếu mua lần đầu thì độ vui vẻ của bạn gái Nam tăng lên \(a_i\) và nếu tiếp tục mua loại hoa \(i\) ở các lần sau, thì độ vui vẻ của bạn gái Nam tằng lên \(b_i\). Nghĩa là, nếu Nam mua \(k\) bông hoa loại thứ \(i\) thì độ vui vẻ của bạn gái Nam tăng lên là \(a_i+(k-1)×b_i.\)

Yêu cầu: Nam muốn chọn mua \(n\) bông hoa từ\( m\) loại hoa để tặng bạn gái sao cho độ vui vẻ của bạn gái Nam là lớn nhất.

Input

• Dòng thứ nhất chứa hai số nguyên \(n,m(1≤n≤10^9,1≤m≤10^9 ).\)

• Dòng thứ \(i\) trong \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \( a_i,b_i (a_i ,b_i≤10^9).\)

Output

• Ghi một số nguyên là độ vui vẻ lớn nhất của bạn giá Nam là lớn nhất.

Sample Input

4 3
5 0
1 4
2 2

Sample Output

14