Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBMARKET - VOI07 Siêu thị may mắn

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbmarket


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.

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 ci và mi 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

Được gửi lên bởi:special_one
Ngày:2008-09-21
Thời gian chạy:0.200s-2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Vietnam Olympiad of Informatics 2007

hide comments
2019-11-22 13:56:24
...

Last edit: 2019-11-22 14:07:55
2018-08-06 09:47:31
code+solution:https://bit.ly/1OFywpr
2017-10-20 11:30:04
BigNum ?
2017-08-22 09:44:05
Kham khảo thuật toán và code:
https://vietcodes.github.io/code/55/
2016-11-14 09:54:26
trâu cũng ... à mà thôi
2016-09-13 16:08:31 hoàng thành
đoạn code này ảo ghê
for i:=1 to n do
for j:=s downto 0 do
if L[j]>0 then
thấy cho Lj ban đầu =0 hết mà ta
2016-08-02 12:55:58
ad xem giúp em bài em bị tle hay wa với, id là 17417436
2016-06-15 11:38:12 xin đừng quên tôi
Tham khảo thuật toán và code tại: http://yeulaptrinh.pw/259/qbmarket-spoj/
2015-01-26 14:50:18 Bee
time limit 10s luôn
2014-12-29 04:42:58 Như Ngọc
AI CÓ THUẬT TOÁN KHÔNG?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.