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.

Dữ liệu vào:

- Dòng đầu tiên hai số \(n\), \(m\) \((n \leq 10^{4},\ 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

Kết quả: Ghi số lượng viên bi nhiều nhất trong \(n\) hộp Bờm mua được.

Ví dụ: