Hè đến, An được về quê chơi. Ở quê, các bạn nhỏ rất thích chơi bắn bi. Vì thế An muốn đi mua bi ở siêu thị về làm quà tặng các bạn. Trong siêu thị có M loại hộp bi khác nhau được đánh số từ 1 đến M. Loại thứ i có a; hộp, mỗi hộp chứa b; viên bi. Giá mỗi hộp là như nhau và An có đủ tiền mua N hộp. An muốn mua được nhiều viên bi nhất có thể.

Yêu cầu: Hãy xác định số viên bi nhiều nhất mà An có thể mua.

Định dạng đầu vào:

Dòng đầu ghi 2 số nguyên N và M (0 < N, M ≤ 1000)

Trên M dòng tiếp theo, mỗi dòng ghi hai số ai, và bi (0 < ai, bi ≤ 1000)

Định dạng đầu ra: Ghi số bi nhiều nhất mà An mua được.

Input 01:

8 4
5 6
2 3
3 4
6 2

Output 01:

42

Input 02:

7 3
3 10
1 5
2 5

Output 02:

45