Ban tổ chức chuẩn bị \(m\) loại quà, số lượng mỗi loại là không hạn chế.

Loại quà thứ \(i\) có hai tham số tính điểm là \(a_i\) và \(b_i\).

Nếu chọn loại quà thứ \(i\) lần đầu tiên, số điểm nhận được là \(a_i\).

Nếu tiếp tục chọn loại quà đó thêm các lần sau, mỗi lần chọn thêm sẽ được cộng \(b_i\) điểm.

Nói cách khác, nếu chọn loại quà thứ \(i\) đúng \(k\) lần thì số điểm nhận được là:

với \(k \ge 1\).

Người chơi được phép chọn đúng \(n\) món quà từ \(m\) loại quà đã chuẩn bị.

Yêu cầu

Hãy tính tổng điểm lớn nhất có thể đạt được khi chọn đúng \(n\) món quà.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 10^9\), \(1 \le m \le 10^5\)).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(a_i\) và \(b_i\) (\(0 \le a_i, b_i \le 10^9\)).

Output

• In ra một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Example

3 3 
7 1 
2 5 
5 0

14

5 3 
5 2 
4 2 
3 1

16