Mr Bin là một cậu bé rất nghịch ngợm và còn rất ham ăn nữa. Một ngày nọ, mẹ cậu vì quá bận bịu nên đã nhờ cậu đi vào siêu thị mua đồ để chuẩn bị cho bữa trưa. Và thật may mắn là nhóc Mr Bin đã hoàn thành nhiệm vụ một cách suất sắc. Mẹ của Mr Bin đã quyết định thưởng cho cậu một món tiền để mua kẹo. Mr Bin hí hửng cầm tiền quay trở lại ngay siêu thị. Với bản tính ham ăn của mình, cậu muốn dùng số tiền mẹ thưởng cho mình để mua được càng nhiều kẹo càng tốt. Nhưng dù rất thông minh thì Mr Bin vẫn chỉ là một học sinh lớp 1, vậy nên chúng ta hãy giúp Mr Bin giải quyết bài toán này nhé.

Yêu cầu:

Cho số tiền \(S\) và danh sách \(N\) loại kẹo có trong siêu thị. Loại kẹo thứ \(i\) giá \(C_i\) đồng mỗi cái và chỉ còn lại \(T_i\) cái. Hãy đưa số kẹo nhiều nhất mà nhóc Mr Bin có thể mua được với số tiền \(S\) trong tay.

Dữ liệu:

• Dòng thứ nhất gồm 2 số nguyên dương \(S, N\).

• \(N\) dòng tiếp theo mỗi dòng gồm 2 số nguyên dương \(C_i, T_i\).

Kết quả:

Gồm một dòng duy nhất là số kẹo nhiều nhất mà nhóc Mr Bin có thể mua được.

Ví dụ:

Giới hạn

• \(S, C_i, T_i \le 10^{18}\)

• \(N \le 10^5\)