FMath khai trương

ĐỀ BÀI: TMATH KHAI TRƯƠNG

Để chuẩn bị cho FMath khai trương, Hiển và Nam đi khảo sát tại \(n\) cửa hàng (\(1 \le n \le 10000\)) để chọn mua đủ \(m\) chiếc máy tính. Tại cửa hàng thứ \(i\), có bán \(a_i\) chiếc máy tính với đơn giá \(b_i\) đồng/máy (\(a_i \le 100, b_i \le 2000\)). Giả sử tổng số máy tính ở tất cả các cửa hàng luôn đủ để mua ít nhất \(m\) chiếc.

Yêu cầu: Tìm cách mua đủ \(m\) chiếc máy tính sao cho tổng số tiền phải trả là nhỏ nhất.

Dữ liệu vào:

• Dòng 1: Chứa hai số nguyên \(m\) và \(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ố nguyên dương \(a_i, b_i\) cách nhau ít nhất một dấu cách.

Kết quả ra:

• Dòng 1: Ghi một số nguyên duy nhất là tổng số tiền nhỏ nhất 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\).

Ví dụ:

Input

22  5
3   30
5   10
6   8
10  5
2   20

Output

168
0
5
6
10
1