문제
N종류의 직선의 나무조각을 이어붙혀서 정확히 길이 L의 펜스를 만드려고 한다. 다시 말해서 사용된 나무조각들의 길이의 합이 정확히 L이 되게 하려 한다.
각 종류의 나무조각은 무한히 사용할 수 있으며, 사용된 나무조각들의 개수를 최소화 하는 프로그램을 작성하라.
제출파일의 이름은 2276.cpp로하고 실행시간은 2초를 넘을 수 없다.
입력
입력파일은 INPUT.TXT로 한다. 첫번째 줄에는 L(10^10 <= L <= 10^18)과 N(1 <= N <= 100)이 입력된다. 그 다음줄에는 각 종류의 나무조각들의 길이가 입력된다. 같은 길이의 나무조각은 2개이상 입력되지 않는다. 나무조각의 길이는 최소 1 최대 100 의 정수다.
출력
출력파일은 OUTPUT.TXT로 한다. 정확히 길이 L의 펜스를 만들 수 있을 경우 최소로 사용하게 되는 나무조각들의 개수를 출력한다. 그렇지 못할 경우 "IMPOSSIBLE"을 출력한다.
예제
1500001 3
23 51 100
15004
힌트
로그인해야 코드를 작성할 수 있어요.