Một công ty muốn mua m máy tính. Sau khi lấy thông tin tại n cửa hàng (1 <=n <= 10000), người ta biết được rằng cửa hàng thứ i có bán a_i máy tính và với giá mỗi máy tính là b_i. (a_i, b_i là những số nguyên dương: a_i <=100; b_i <= 2000).

Giả sử rằng các cửa hàng có đủ máy để bán cho công ty. Hãy tìm cách mua rẻ nhất.

Dữ liệu: Vào từ file văn bản BUY.INP

• Dòng 1: Chứa hai số m, n cách nhau ít nhất một dấu cách.
• n dòng tiếp theo, dòng thứ i chứa hai số a_i, b_i cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản BUY.OUT

• Dòng 1: Ghi tổng số tiền phải trả.
• n dòng tiếp theo, dòng thứ i ghi số máy tính mua ở cửa hàng thứ i.