Opening Day 2

Haebin loves jajangmyeon so much that he opened a Chinese restaurant that sells nothing else. He is ambidextrous, so a single cooking can use up to two woks at the same time.

Haebin hates waste, so every wok he uses is filled to its exact capacity. Cooking with one wok of size $s$ produces exactly $s$ bowls, and cooking with two woks of sizes $s$ and $t$ at the same time produces exactly $s+t$ bowls. A single cooking cannot use the same wok twice, but if Haebin owns two or more woks of the same size, he can use two of them together. Every wok is available again for the next cooking.

The order is $N$ bowls, and the bowls produced by all of the cookings must add up to exactly $N$. Write a program that finds the smallest number of cookings that fills the order.

The first line has the number of bowls ordered $N$ and the number of woks Haebin owns $M$, separated by a space. ($1 \le N \le 10000$, $1 \le M \le 1000$)

The second line has the wok sizes $S_1, S_2, \dots, S_M$, separated by spaces. ($1 \le S_i \le N$) Haebin may own several woks of the same size.

Print the minimum number of cookings needed to fill the whole order. If no combination of cookings produces exactly $N$ bowls, print -1.

Consider making 6 bowls with one wok of size 1 and one wok of size 3. Cook 3 bowls in the size 3 wok, then cook 3 more bowls in the same wok, and 6 bowls are done in two cookings. A wok can be reused in every later cooking, but only two different woks can go into one cooking.