An được mời tham gia trò chơi “Siêu thị may mắn” do đài truyền hình ZTV tổ chức.

Siêu thị được đặt trong trường quay truyền hình có n mặt hàng được đánh số từ 1 đến n và mặt hàng thứ i được niêm yết giá là c_i đồng, i = 1, 2, ..., n.

Theo thể lệ của trò chơi, An được ban tổ chức tặng một thẻ mua hàng có giá trị là s đồng và phải dùng hết số tiền trong thẻ này để mua hàng trong siêu thị với điều kiện mặt hàng thứ i chỉ được mua với số lượng nhiều nhất là m_i, i = 1, 2, …, n.

An sẽ là người thắng cuộc nếu tìm được tổng số cách mua hàng thỏa mãn yêu cầu đặt ra và chỉ ra một cách mua hàng nếu có.

Yêu cầu: Hãy giúp An trở thành người thắng cuộc khi cho bạn biết trước các giá trị n, s, c_i và m_i (1 ≤ n ≤ 500; 1 ≤ s ≤ 10⁵; 1 ≤ c_i ≤ 10⁴; 1 ≤ m_i ≤ 100) với i = 1, 2, …, n.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên dương s và n.
Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên dương c_i và m_i với i = 1, 2, …, n.

Kết quả

Gồm 1 dòng duy nhất ghi số nguyên d là tổng số cách mua hàng tìm được.