Ngày lễ vu lan báo hiếu vừa qua nhưng vì đã không ở nhà, Tom cảm thấy nên tặng mẹ thứ gì đó để mẹ vui. Cậu quyết định mua tặng mẹ ~n~ bông hoa. Tom đến một cửa hàng hoa địa phương để tiến hành chọn hoa. Tại cửa hàng, có ~m~ loại hoa khác nhau và số lượng là vô hạn. Tại đây, với mỗi loại hoa, nếu mua lần đầu, độ vui vẻ của mẹ Tom tăng lên ~a_i~ và nếu tiếp tục chọn mua loại hoa đó, độ vui vẻ của mẹ Tom sẽ tăng lên ~b_i~. Tóm lại, nếu Tom chọn mua k > 0 bông hoa loại ~i~, độ vui vẻ của mẹ Tom sẽ tăng lên ~a_i~ +~(k - 1)*b_i~. Tom muốn chọn ~n~ bông hoa từ ~m~ loại hoa sao cho độ vui vẻ của mẹ cậu là nhiều nhất. Tuy nhiên vì còn bận nhiều việc, bạn hãy giúp Tom nhé!

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~n, m~ (~1 \le n \le 10^9, 1 \le m \le 10^9~). Số món quà Tom muốn mua và số loại hoa tại cửa hàng
• Dòng thứ ~i~ trong ~m~ dòng sau chứa hai số nguyên ~a_i~ và ~b_i~ (~0 \le a_i, b_i \le 10^9)~ thông tin loại hoa thứ ~i~.

Kết quả

Xuất ra độ vui vẻ lớn nhất của mẹ Tom sau khi chọn ~n~ bông hoa.

Sample Input 1

4 3
5 0
1 4
2 2

Sample Output 1

14

Sample Input 2

5 3
5 2
4 2
3 1

Sample Output 2

14

Giải thích

• Ở ví dụ đầu tiênm Tom chọn 1 bông hoa loại 1 và 3 bông hoa loại 2, độ vui vẻ của mẹ Tom sẽ là ~5 + (1 +2 * 4) = 14~
• Ở ví dụ đầu tiênm Tom chọn 2 bông hoa loại 1 và 2 bông hoa loại 2 và 1 bông hoa loại 3 độ vui vẻ của mẹ Tom sẽ là ~(5 + 1 * 2+ + (4 +1 * 2) + 3 = 16~