Problem
Enchanted Land에서는 A
1, A
2,..., A
M 단위의 동전이 사용됩니다. 그 마술사는 가게에 와서 각 액면가의 동전이 정확히 두 개씩 있는 것을 발견했습니다. 그는 금액 N을 지불해야 합니다. 거스름돈 없이 지불할 수 있는지 결정하는 프로그램을 작성하십시오.
입력
프로그램의 입력에서 먼저 숫자 N(1 <= N <= 10
9)이 나온 다음 숫자 M(1 <= M <= 15), 그리고 M 쌍별 고유 숫자 A
1 , A
2,..., A
M (1 <= A
i <= 10
9 ).
출판물
첫 번째 인쇄 K - Magic Man이 지정된 금액을 변경 없이 지불할 수 있는 경우 제공해야 하는 동전의 수입니다. 그런 다음 동전의 가치를 정의하는 K 숫자를 인쇄하십시오. 솔루션이 여러 개인 경우 Magic Man이 가능한 한 가장 적은 수의 동전을 제공하는 변형을 인쇄하십시오. 이러한 옵션이 여러 개인 경우 그 중 하나를 인쇄하십시오.
거스름돈 없이는 할 수 없다면 하나의 숫자 0을 인쇄하십시오. 마술사가 지정된 금액을 지불할 돈이 충분하지 않으면 하나의 숫자 -1(마이너스 1)을 인쇄하십시오.
<몸>
| 입력 |
출력 |
100 6
11 20 30 40 11 99
| 3
40 30 30
|