SPMARKET - Siêu thị may mắn (VOI2007)
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

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à ci đồ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à mi, 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, ci và mi (1 ≤ n ≤ 500; 1 ≤ s ≤ 105; 1 ≤ ci ≤ 104; 1 ≤ mi ≤ 100) với i = 1, 2, …, n.

Dữ liệu

Dòng đầu tiên chứa hai số nguyên dương sn.
Dòng thứ i trong n dòng tiếp theo chứa hai số nguyên dương ci và mi 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.

Ví dụ

Input

12 3
4 1
6 2
2 1

Output

2


Nguồn: VOI 2007

Back to Top