개업 2

해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다. 해빈이는 양손잡이여서 한 번 요리할 때 웍(중국 냄비)을 두 개까지 동시에 쓸 수 있다.

해빈이는 낭비를 싫어해서 웍을 항상 용량만큼 꽉 채워 쓴다. 크기가 $s$인 웍 하나로 요리하면 정확히 $s$그릇이 나오고, 크기가 $s$와 $t$인 웍 두 개를 동시에 쓰면 정확히 $s+t$그릇이 나온다. 한 번의 요리에 같은 웍을 두 번 넣을 수는 없지만, 크기가 같은 웍을 두 개 이상 가지고 있다면 그중 두 개를 함께 쓸 수 있다. 웍은 요리가 끝나면 다음 요리에 다시 쓸 수 있다.

주문받은 그릇 수가 $N$일 때, 모든 요리에서 나온 그릇 수의 합이 정확히 $N$이어야 한다. 최소 몇 번의 요리로 주문을 처리할 수 있는지 구하는 프로그램을 작성하시오.

첫째 줄에 해빈이가 주문받은 짜장면의 그릇 수 $N$과 가지고 있는 웍의 개수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 10000$, $1 \le M \le 1000$)

둘째 줄에 웍의 크기 $S_1, S_2, \dots, S_M$이 공백으로 구분되어 주어진다. ($1 \le S_i \le N$) 크기가 같은 웍을 여러 개 가지고 있을 수도 있다.

모든 주문을 처리하는 데 필요한 최소 요리 횟수를 출력한다. 어떤 방법으로도 정확히 $N$그릇을 만들 수 없으면 -1을 출력한다.

크기가 1, 3인 웍 하나씩으로 6그릇을 만드는 경우를 보자. 3그릇짜리 웍으로 한 번 요리하고 같은 웍으로 다시 한 번 요리하면 두 번 만에 6그릇이 된다. 웍은 요리마다 다시 쓸 수 있지만, 한 번의 요리에 함께 넣을 수 있는 것은 서로 다른 웍 두 개뿐이다.