문제
밀가루 쇼핑몰을 운영하는 한국이는 매일 밀가루 포장 때문에 머리가 터질 것만 같았다. 모든 박스는 용량이 정해져 있어서 용량을 초과하여 담을 수 없을 뿐 아니라 용량보다 부족하게 담을 경우에는
배송과정에서 박스가 터지는 사고가 발생될 수 있기 때문에 박스의 용량에 맞도록 정확하게 물건을 담아야 한다.
주문한 용량에 꼭 맞는 박스가 있다면 다행이지만 그렇지 않을 경우에는 여러 박스에 나누어 담아서 주문한 용량과 꼭 맞게 포장을 해야 한다.
그런데 박스의 숫자가 많아질수록 택배비가 많이 들기 때문에 박스의 개수를 최소가 되게 해야 한다.
예를 들어 박스의 종류가 2가지이고 용량이 각각 3kg, 5kg이라고 할 때 18kg을 담기 위해서는
3kg박스 6개에 담을 수도 있지만 5kg박스 3개와 3kg박스 1개에 담으면 4개의 박스로 배송이 가능해진다. 발송해야 할 밀가루의 양과 박스의 종류, 각 박스의 용량이 주어질 때 밀가루를 발송하기 위해
필요한 박스의 최소개수를 구하는 프로그램을 작성하라.
각 용량별 박스의 개수는 무제한 있다고 가정을 한다.
입력
첫 줄에 주문받은 밀가루의 양 N(1≤N≤10000)이 주어진다.
둘째 줄에는 박스의 종류 M(1≤M≤10)이 주어진다.
셋째 줄부터 M줄에 걸쳐 박스의 용량을 나타내는 정수 S_i(1≤S_i≤1000)가 주어진다.
출력
밀가루를 배송하기 위해 필요한 박스의 최소 개수를 출력한다.
만약 주문받은 양을 정확하게 박스에 담을 수 없을 경우에는 -1을 출력한다.
예제
18
2
3
5
4
출처
2014 ICT Award KOREA
로그인해야 코드를 작성할 수 있어요.