문제 설명
여러분은 실력을 인정받아 전 세계적으로 사용할 수 있는 자동판매기용 프로그램의 개발을 의뢰받았다. 거스름돈에 사용될 동전의 수를 최소화하는 것이다.
입력으로 거슬러 줘야할 돈의 액수와 그 나라에서 이용하는 동전의 가짓수 그리고 동전의 종류가 들어오면 여러 가지 방법들 중 가장 적은 동전의 수를 구하는 프로그램을 작성하시오.
입력으로 거슬러 줘야할 돈의 액수와 그 나라에서 이용하는 동전의 가짓수 그리고 동전의 종류가 들어오면 여러 가지 방법들 중 가장 적은 동전의 수를 구하는 프로그램을 작성하시오.
입력 설명
첫 번째 줄에는 거슬러 줘야할 돈의 액수 m이 입력된다.
(0<=m<=10,000)
다음 줄에는 그 나라에서 사용되는 동전의 종류의 수 n이 입력된다.
(0<=n<=4)
마지막 줄에는 동전의 수만큼의 동전 액수가 오름차순으로 입력된다.
(100<=액수<=2,147,483,647)
(0<=m<=10,000)
다음 줄에는 그 나라에서 사용되는 동전의 종류의 수 n이 입력된다.
(0<=n<=4)
마지막 줄에는 동전의 수만큼의 동전 액수가 오름차순으로 입력된다.
(100<=액수<=2,147,483,647)
출력 설명
최소의 동전의 수를 출력한다.
(단, 거슬러 줘야할 돈을 그 어떠한 동전으로도 온전히 바꿀 수 없다면 IMPOSSIBLE을 출력한다. 또한, m=0이어도 0원을 만들 수 있다면 0원을 만드는 동전의 개수를 출력해야한다.)
(단, 거슬러 줘야할 돈을 그 어떠한 동전으로도 온전히 바꿀 수 없다면 IMPOSSIBLE을 출력한다. 또한, m=0이어도 0원을 만들 수 있다면 0원을 만드는 동전의 개수를 출력해야한다.)
입력 예시 Copy
1050
4
150 200 250 300
출력 예시 Copy
4