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

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
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?
2013-12-21 05:39:36 code quá nhanh ...
test quá yếu, thật sự rất thất vọng vs ps bài này, thử test MAX ko có cách gì qua time limit nổi :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.