Năm 2020, Để chuẩn bị cho \(TMath\) khai trương, thầy Toàn giao cho 2 cộng sự thân tín là Tú và Vương đi chọn mua \(m\) máy tính. Sau một buổi lóc cóc, rong ruổi trên chiếc đạp xe cũ Thống Nhất màu xanh, hai bạn đã khảo sát một vòng quanh thành phố, lấy thông tin tại \(n\) cửa hàng \((1 \leq n \leq 10000)\), Tú và Vương 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 \leq 100; b_i \leq 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 giúp Tú và Vương để mua được với giá rẻ nhất .

INPUT:

• 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.

OUTPUT:

• 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\).

Example

Sample Input

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

Sample Output

168
0
5
6
10
1