QBMARKET - VOI07 Siêu thị may mắn
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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 5 ; 1 ≤ c i ≤ 10 4 ; 1 ≤ m i ≤ 100) với i = 1, 2, …, n.
Input
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.
Output
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.
Example
Input: 12 3 4 1 6 2 2 1 Output: 2
- Người up: cun
- Nguồn bài: Vietnam Olympiad of Informatics 2007