CF788C The Great Mixing

Sasha 和 Kolya 决定再次用可乐把自己灌醉。这次他们有 $k$ 种可乐，第 $i$ 种的可乐二氧化碳浓度为 $\frac{a_i}{1000}$。今天，在温哥华 Sergiy 的派对上，他们决定调一杯二氧化碳浓度为 $\frac{n}{1000}$ 的可乐。饮料必须美味，因此每种可乐类型在杯中只能加入整数升（某些类型可以不加入）。此外，他们希望杯中的可乐总体积最小。 二氧化碳浓度的定义是可乐中二氧化碳的体积除以可乐的总体积。当混合两种可乐时，二氧化碳的总体积相加，可乐的总体积也相加。 请帮助他们找到制备二氧化碳浓度为 $\frac{n}{1000}$ 的可乐所需的最小自然数升数。假设朋友们每种可乐类型的供应是无限的。

第一行包含两个整数 $n,k$（$0 \leq n \leq 1000$，$1 \leq k \leq 10^6$），表示朋友们想要的二氧化碳浓度和可乐类型的数量。 第二行包含 $k$ 个整数 $a_1, a_2,\dots, a_k$（$0 \leq a_i \leq 1000$），表示每种可乐类型的二氧化碳浓度。某些可乐类型的浓度可能相同。

输出制备二氧化碳浓度为 $\frac{n}{1000}$ 的可乐所需的最小自然数升数。如果不可能，则输出 $-1$。

在第一个示例中，我们可以通过混合 1 升 $\frac{300}{1000}$ 和 1 升 $\frac{500}{1000}$ 的可乐来达到浓度 $\frac{400}{1000}$：$\frac{300+500}{1000+1000} = \frac{400}{1000}$。 在第二个示例中，我们可以通过混合 2 升 $\frac{25}{1000}$ 和 1 升 $\frac{100}{1000}$ 的可乐来达到浓度 $\frac{50}{1000}$：$\frac{25+25+100}{3 \cdot 1000} = \frac{50}{1000}$。