Problem
Di Enchanted Land, syiling denominasi A
1, A
2,..., A
M digunakan. Lelaki silap mata itu datang ke kedai dan mendapati dia mempunyai tepat dua keping syiling bagi setiap denominasi. Dia perlu membayar jumlah N. Tulis program untuk menentukan sama ada dia boleh membayar tanpa perubahan.
Input
Pada input program mula-mula datang nombor N (1 <= N <= 10
9), kemudian nombor M (1 <= M <= 15) dan kemudian M nombor berbeza berpasangan A
1 , A
2,..., A
M (1 <= A
i <= 10
9 ).
Cetakan
Cetakan pertama K - bilangan syiling yang perlu diberikan oleh Lelaki Sihir jika dia boleh membayar jumlah yang ditentukan tanpa perubahan. Kemudian cetak nombor K yang menentukan nilai syiling. Jika terdapat beberapa penyelesaian, cetak varian di mana Magic Man memberikan bilangan syiling terkecil yang mungkin. Jika terdapat beberapa pilihan sedemikian, cetak mana-mana daripadanya.
Jika anda tidak boleh melakukan tanpa perubahan, kemudian cetak satu nombor 0. Jika Lelaki Sihir tidak mempunyai wang yang cukup untuk membayar jumlah yang ditentukan, cetak satu nombor -1 (tolak satu).
| Input |
Output |
100 6
11 20 30 40 11 99
| 3
40 30 30
|