Cây khế

Điểm số: 1

Giới hạn thời gian: 1s

Giới hạn bộ nhớ: 512 MB

Người đăng: admin

Đề bài:

Câu chuyện Cây khế chắc có lẽ đã quen thuộc với các bạn. Nhưng các bạn có biết đến phần hai của câu chuyện? Phần hai của câu chuyện thể hiện tính nhân văn và giáo dục cao. Chuyện kể rằng:

Sau khi tham lam lấy rất nhiều vàng ở phần 1, người anh rơi xuống vực thẳm nhưng anh ta chợt nghe thấy tiếng gọi của vợ. Anh chợt bừng tỉnh, hoá ra đó chỉ là một giấc mơ. Sau giấc mơ đó, anh đã hối hận khi may chiếc túi quá to, và quyết định nghe theo lời chim thần, chỉ may túi 3 gang mà thôi. Tuy nhiên lòng tham thì cũng khó cưỡng, nên khi đến nơi lấy châu báu, anh quyết định tính toán thật kỹ lưỡng để làm sao không lãng phí cái túi một chút nào. Số lượng châu báu, vàng bạc ở đây là vô số kể, giá trị không biết bao nhiêu mà đếm, chỉ có thể phân biệt bằng cân mà thôi.

Túi của anh ta có thể chứa được tối đa là N (kg), Châu báu có M loại, mỗi loại không giới hạn số lượng, và có trọng lượng lần lượt là C1, C2,…, Cm.

Anh ta muốn mang mang được đúng N (kg) châu báu về nhà. Bạn hãy giúp anh ta đếm xem có bao nhiêu cách làm nhé.

 

Đầu vào:

-  Dòng đầu tiên là 2 số nguyên dương N, M (N<=250, M<=50)

-  Dòng tiếp theo là C1, C2, …, Cm. (0 < Ci <=50)

 

Đầu ra:

-  Một số nguyên duy nhất là số cách lấy châu báu sao cho có khối lượng đúng bằng N.

 

Ví dụ:

Input

Output       

4 3

1 2 3

4

 

Giải thích: Có các cách mang: (1,1,1,1), (1,1,2), (1,3), (2,2).