Problem
Ở Vùng đất mê hoặc, các đồng xu có mệnh giá A
1, A
2,..., A
M được sử dụng. Người đàn ông phù thủy đến cửa hàng và thấy rằng anh ta có đúng hai đồng xu của mỗi mệnh giá. Anh ta cần trả số tiền N. Viết chương trình để xác định xem anh ta có thể trả mà không thay đổi hay không.
Đầu vào
Tại đầu vào của chương trình đầu tiên là số N (1 <= N <= 10
9), sau đó là số M (1 <= M <= 15) và sau đó là M các số phân biệt theo cặp A
1 , A
2,..., A
M (1 <= A
i <= 10
9).
Dấu ấn
Đầu tiên in K - số xu mà Magic Man sẽ phải đưa ra nếu anh ta có thể trả số tiền được chỉ định mà không thay đổi. Sau đó in ra K số xác định giá trị của các đồng xu. Nếu có một số giải pháp, hãy in phương án trong đó Magic Man đưa ra số lượng xu nhỏ nhất có thể. Nếu có một số tùy chọn như vậy, hãy in bất kỳ tùy chọn nào trong số chúng.
Nếu bạn không thể làm mà không thay đổi, thì hãy in một số 0. Nếu Magic Man không có đủ tiền để trả số tiền đã chỉ định, hãy in một số -1 (trừ một).
| Đầu vào |
Đầu ra |
100 6
11 20 30 40 11 99
| 3
40 30 30
|