Bờm đi siêu thị, trong siêu thị có ~M~ loại màu bi khác nhau, loại bi màu ~i~ có ~a_i~ hộp, mỗi hộp có ~b_i~ viên bi. Giá mỗi hộp bi là như nhau. Bờm cần mua ~N~ hộp bi để tổng số bi trong ~N~ hộp là nhiều nhất.

Yêu cầu: Cho ~N~ là số hộp bi Bờm cần mua và ~M~ là số màu các hộp bi. Hãy lập trình giúp Bờm chọn ~N~ hộp bi sao cho tổng số bi mua được là nhiều nhất.

Input

Vào từ tệp văn bản CHONBI.INP:

• Dòng đầu tiên hai số ~N, M~ ~(N, M \leq 10^4)~.

• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm hai số ~a_i~ và ~b_i~ ~(1 \leq a_i, b_i \leq 10^5)~.

• Dữ liệu vào đảm bảo luôn đủ ~N~ hộp để Bờm mua.

Output

Ghi ra file CHONBI.OUT:

• Một dòng gồm số lượng viên bi nhiều nhất trong ~N~ hộp Bờm mua được.

Sample Input 1

7 3
5 10
2 5
3 6

Sample Output 1

62