Sasha 和 Kolya 决定再次喝可乐喝醉。这次他们有 k 种可乐。第 i 种类型的特征在于其二氧化碳浓度 $${ \frac { a _ { i } } { 1 0 0 0 } }$$。今天,在纪念温哥华 Sergiy 的聚会上,他们决定准备一杯二氧化碳浓度为 $$\frac{n}{1000}$$ 的可乐。饮料也应该是美味的,因此玻璃杯只能容纳整数升的每种可乐类型(某些类型不能出现在玻璃杯中)。此外,他们还希望最大限度地减少玻璃杯中可乐的总体积。
二氧化碳浓度定义为焦炭中二氧化碳的体积除以焦炭的总体积。当您混合两种可乐时,二氧化碳的体积会相加,可乐的总体积也会相加。
帮助他们,找到制造二氧化碳浓度为 $$\frac{n}{1000}$$ 的玻璃所需的最小自然升数。假设朋友们每种可乐的数量都是无限的。
输入
第一行包含两个整数n,k(0 ≤ n ≤ 1000, 1 ≤ k ≤ 106)——朋友们想要的二氧化碳浓度和可乐种类的数量。
第二行包含 k 个整数 a1, a2, ..., ak (0 ≤ ai ≤ 1000) – 每种可乐的二氧化碳浓度。某些可乐类型可以具有相同的浓度。
输出
打印出制备二氧化碳浓度 $$\frac{n}{1000}$$ 的玻璃所需的最小自然升数,如果不可能,则打印 -1。
示例
输入 #1
400 4 100 300 450 500
输出 #1
2
输入 #2
50 2 100 25
输出 #2
3
注意
在第一个示例案例中,我们可以使用一升 $$\frac{300}{1000}$$ 和 $${ \frac { 5 0 0 } { 1 0 0 0 } }$$ 类型的可乐来达到浓度 $$\frac{400}{1000}$$: $$\frac{300+500}{1000+1000}=\frac{400}{1000}$$。
在第二种情况下,我们可以使用两升 $${ \frac { 2 5 } { 1 0 0 0 } }$$ 类型和一升 $${ \frac { 1 0 0 } { 1 0 0 0 } }$$ 类型来实现浓度 $${ \frac { 5 0 } { 1 0 0 0 } }$$ 类型: $$\frac{25+25+100}{3\cdot 1000} = \frac{50}{1000}$$。