Cửa hàng có ~m~ loại quà, mỗi loại có số lượng không giới hạn. Với loại quà thứ ~i~, món đầu tiên được chọn mang lại độ vui ~a_i~, mỗi món tiếp theo cùng loại mang lại độ vui ~b_i~.

Bạn cần chọn đúng ~n~ món quà. Hãy tìm tổng độ vui lớn nhất có thể đạt được.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, m~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i, b_i~.

Output

In ra một số nguyên duy nhất là tổng độ vui lớn nhất.

Giới hạn

• ~a_i, b_i \ge 0~
• Kết quả không vượt quá phạm vi số nguyên 64 bit có dấu.

Vào/ra bằng file

• Dữ liệu vào: đọc từ file CHONQUA.INP.
• Kết quả: ghi ra file CHONQUA.OUT.