You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

一瓶saSha可乐一升。有k种saSha可乐，第i种saSha可乐含碳量为ai/1000。ai为整数。现在需要从这k种可乐里分别选若干瓶可乐(可以选多种可乐，每种可乐有无限瓶，所以每种可乐可以选择任意瓶)，混合起来，构造一桶含碳量为n/1000的特殊可乐。混合的时候，一瓶可乐不能只用一部分(例如用半瓶或者0.3瓶)，必须用整瓶来混合。两瓶可乐混合后，含碳量相加，体积变两升。

请问最少能用多少瓶可乐，构造出一桶特殊可乐。

输入(coke.in)

第一行2个整数n,k。第二行k个整数，a1,a2,…,ak。

输出(coke.out)

一行整数，最少需要多少瓶saSha可乐构造出特殊可乐。如果无法构造出特殊可乐，输出-1.

样例输入1

400 4

100 300 450 500

样例输出1

2

样例解释1

选择一瓶第2种sasha可乐，一瓶第4种sasha可乐。共两瓶可乐。

(300+500)/(1000+1000)=400/1000

样例输入2

50 2

100 25

样例输出2

3

选择一瓶第1种sasha可乐，选择两瓶第二种sasha可乐。共3瓶可乐。

(100+25+25)/(1000+1000+1000)=50/1000

数据范围：

30% k<=20

60% k<=100

100% 1<=k<=10^6, 0<=n<=1000,0<=ai<=1000