cs_102 Bài toán đổi tiền

Cho n loại tiền giấy có mệnh giá là a1 đến an. Tm cách đổi S đồng thành ít tờ gồm các loại tiền trên. Nghĩa là tìm các cách sao cho k1.a1 + k2.a2 + … + kn.an = S (ki>=0 với mọi i ) mà tổng k1+k2+…+kn nhỏ nhất. Biết số lượng mỗi loại tiền không hạn chế.

Dữ liệu vào

• Dòng đầu tiên ghi 2 số S và n ( 0<=S<=10000, 0<n<=100); • Dòng tiếp theo ghi n số, tương ứng với mệnh giá của đồng tiền i (a_i<=250). </p>

Kết quả ghi ra

• Dòng đầu ghi tổng số tờ của cách đổi ít tờ nhất. • Các dòng tiếp theo, mỗi dòng ghi 2 số: số hiệu và số lượng của một loại tiền được đổi.

INPUT1

35 3

1 2 4

OUTPUT1

10 1 1 2 1 3 8