VOI 07 Bài 2 - Siêu thị may mắn

View as PDF

Submit solution

Points: 1.33 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Vietnam Olympiad of Informatics 2007
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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, \dots, 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, \dots, 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 \leq n \leq 500;\; 1 \leq s \leq 10^{5}; \; 1 \leq c_{i} \leq 10^{4};\; 1 \leq m_{i} \leq 100)~ với ~i = 1, 2, \dots, 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, \dots, 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.

Sample Input

12 3
4 1
6 2
2 1

Sample Output

2

Comments

Please read the guidelines before commenting.



  • 7
    leduykhongngu   commented on Dec. 7, 2021, 9:14 a.m.

    Lưu ý: Bài này kết quả có thể rất lớn, tuy nhiên trong bộ test thì kết quả không quá số nguyên 128 bit.

    Việc thêm test có kết quả lớn sẽ khiến bài tập này không thể AC được với TL hiện tại. Do đây là đề thi quốc gia nên bọn mình cũng sẽ không cập nhật đề.